时间限制： 1.0 秒

空间限制： 2048 MB 512 MB

题目描述

小 B 是一个电影迷，只要有时间，她就要去观摩最新的大片。但她不喜欢自己在电脑或其他电子设备上观看，而是喜欢去电影院，因为她觉得那里更有气氛。

由于工作关系，小 B 这次被派到 A 地一段时间，她发现这里的电影院和她熟悉的模式完全不同。

电影院内部都是正方形的，一共有 $k$ 排，从前到后按照 $1$ 到 $k$ 编号，每排内有 $k$ 个座位，从左到右按照 $1$ 到 $k$ 编号，其中 $k$ 为奇数。

考虑到安全因素，座位不允许购票者自行挑选，而是由售票人员通过电脑程序确定。由于大家都希望有更好的观影效果，因此一般都倾向于选择更靠近影院中心的座位。电脑程序选择座位的过程为：

• 如果有人需要购买 $m$ 张电影票，程序首先会确定一个排号 $x$，并从中选择一段连续且尚未售出的座位号 $[l,r]$，其中 $r-l+1=m$。
• 如果没有任何一排中有 $m$ 个连续的空座位，则电脑程序会报错，在这个购票请求中将不会卖出任何票。

在保证选出的座位在同一排且座位号连续的前提下，程序会选择最“接近中心”的座位。

具体来说，令 $x_c=y_c=\frac{k+1}{2}$，表示影院中最中心的座位。定义选出的这些座位到影院中心的距离函数为：

最“接近中心”的座位为能最小化上述函数的座位。若有多个可选座位均满足离影 院中心距离最小的条件，则选座程序优先选择靠前的座位（即排号 $x$ 最小的座位）。若仍有多个座位符合要求，则选座程序优先选择靠左的座位（即座位号 $l$ 值最小的座位）。

假设电影院最开始没有售出任何座位，小 B 希望知道对于给出的 $n$ 个购票请求，每次售出的票都能买到哪些座位？

输入格式

从标准输入读入数据。

本题包含多组测试数据，你需要用判断是否读到文件末尾的形式判断输入是否结束。

每组数据的第一行包含两个正整数 $n$ 和 $k$，表示购票请求的数量和影院大小。保证 $1 \le n \le 3 \times 10^5, 1 \le k \le 3\times 10^5+1$，且 $k$ 为奇数。

第二行为空格分隔的 $n$ 个正整数，其中第 $i$ 个数为 $m_i$（$1\le i\le n$），表示每次要求购买的票数，保证 $1\le m_i\le k$。

输出格式

输出到标准输出。

对于每组测试数据：

输出 $n$ 行，每个购买请求结果为一行。

如果无法在一排中买到 $m_i$ 个连续的座位，则在对应的行中输出 $-1$。否则输出三个空格分隔的整数 $x,l,r$，为所买电影票的排号和起止座位号。

2 1
1 1
4 3
1 2 3 1

1 1 1
-1
2 2 2
1 1 2
3 1 3
2 1 1

样例 2

见题目文件区的 2.in 和 2.ans。

子任务

对于所有数据，保证：

• $n\le 3\times 10^5,k\le 3\times 10^5+1$，且 $k$ 为奇数；
• 每个测试点的数据组数不超过 5 组。