1.5s | movie.cpp/in/out | 512MB

题目描述

最近小 B 在电影院做收银员给自己攒些零花钱。电影院的座位可以抽象成一个 $k \times k$ 的矩阵，保证 $k$ 是奇数。其中心位置 $(\frac{k+1}{2} , \frac{k+1}{2})$ 是观影效果最好的一个位置，某个位置 $(x,y)$ 的观影效果为这个点到中心位置的曼哈顿距离 $|x - \frac{k+1}{2}| + |y - \frac{k+1}{2}|$，这个值越小意味着观影效果越好。

最近由 China Cinema Foundation 组织拍摄的大片《IOI2020·中国选手的AK之路》正在热映，有 $n$ 个团队依次来购买电影票。第 $i$ 个团队有 $m_i$ 个人，他们希望能够购买一排 $m_i$ 个连续的座位，并且满足这个要求的基础上要求所有人的观影效果和尽可能小。

形式化地，小 B 需要选出一个位置 $(x,l)$ 满足 $1 \leq x \leq k , 1 \leq l \leq k - m_i + 1$，且设 $r = l + m_i - 1$，则 $(x,l),(x,l+1),\ldots,(x,r)$ 这些座位的票都没有被购买。

这样的 $(x,l)$ 有很多种，你需要在所有方案中选择 $\sum\limits_{i=l}^r |x-\frac{k+1}{2}| + |i - \frac{k+1}{2}|$ 最小的方案。如果此时仍有多种方案，则优先选择 $x$ 最小的方案；如果在考虑 $x$ 的情况下仍有多种方案，则选择 $l$ 最小的方案。确定了 $(x,l)$ 之后，你将 $(x,l),(x,l+1),\ldots,(x,r)$ 座位的电影票卖给这个团队。如果不存在合法的 $(x,l)$，那么他们只好放弃这次观影。

假设在第一个团队购买之前所有座位都没有被购买，小 B 已经忙不过来了，所以希望你帮他算一算。

输入格式

第一行两个整数 $n,k$ 表示团队数量和影院大小。

第二行 $n$ 个整数 $m_1,m_2,\ldots,m_n$ 表示每个团队的人数。

输出格式

对于每个团队输出一行，如果没有买到电影票输出 -1，否则输出三个整数 $x,l,r$ 表示该团队买到的座位。

样例输入

7 3
1 2 1 2 1 2 1

样例输出

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

数据范围与特殊性质

对于所有数据，$1 \leq n \leq 4 \times 10^5 , 1 \leq m_i \leq k \leq 300001 , k$ 是奇数。

测试点编号