Berland的所有电影院都是长方形,每排有K排K个座位,K是奇数。行数和座位号从1到K。出于安全考虑,前来售票处购票的人不得自行选择座位。以前,选择是由收银员做出的,但现在这是由特殊座位计划负责的。研究发现,绝大多数伯兰居民去电影院是为了看电影,这就是为什么他们想坐在尽可能靠近大厅中心的位置。而且,一队M人来看电影,必然要占据一排连续的M个座位。让我们制定一个算法,程序根据该算法选择座位并售票。当 M 个座位的请求到来时,程序应确定行号 x 以及该行中座位号的段 [yl, yr],其中 yr - yl + 1 = M。从所有这些可能的变体中,程序应选择总座位距中心距离函数值最小的一个作为最终结果。假设 $$x_{c} = \left\lceil \frac{k}{2} \right\rceil, y_{c} = \left\lfloor \frac{k}{2} \right\rfloor$$ — 最“中心”座位的排号和座位号。那么座位距大厅中心距离的函数值为$$\sum_{y=y_1}^{y_r}|x-x_c|+|y-y_c|$$。如果最小函数值的数量超过 1,则程序应选择距离屏幕较近的一个(即行号 x 较低)。如果变体仍然有多个,则应选择 yl 最小的一个。如果你还没有得到,你的任务是模拟这个程序的工作。
输入
第一行包含两个整数 N 和 K (1 ≤ N ≤ 1000, 1 ≤ K ≤ 99) — 分别是请求量和大厅大小。第二行包含 N 个空格分隔的整数 Mi,范围为 [1, K] — 对程序的请求。
输出
输出 N 行。在第i行输出“-1”(不带引号),如果不可能在一行中找到Mi连续的座位,否则输出三个数字x,yl,yr。用空格分隔数字。
示例
输入 #1
2 1 1 1
输出 #1
1 1 1 -1
输入 #2
4 3 1 2 3 1
输出 #2
2 2 2 1 1 2 3 1 3 2 1 1