最近,波利卡普一直是电影新奇事物的粉丝,并试图不要错过它们!
在不久的将来,将发布$$$n$$$新电影:其中$$$i$$$将从$$$a_i$$$日到$$$b_i$$$日播出。这意味着,如果波利卡普想要在电影院观看第 $$$i$$$ 部电影,他必须在从 $$$a_i$$$ 到 $$$b_i$$$(含)期间观看。
如果 Polycarp 没有机会在电影院观看电影,他可以在 $$$b_i$$$ 之后通过在线服务观看电影。当然,这对于波利卡普来说是一个不希望有的结果,因为全世界将有时间在社交网络上讨论这部电影!
Polycarp 每天只能观看不超过 $$$m$$$ 的电影。帮助波利卡普找到一个观影时间表,这样每部电影都可以在电影院观看。如果这样的时间表不存在,那么波利卡普想要看电影,以便:
- 对于他没有时间在电影院观看的每一部电影,我们会找到其播放结束与Polycarpus观看电影的日期之间的天数,
- 前一点的最大值应尽可能小。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 输入中测试用例的数量。以下是 $$$t$$$ 测试用例的描述。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le m \le 10^9$$$) — 电影数量以及 Polycarp 每天可以观看的最大电影数量。
在接下来的 $$$n$$$ 行中,每行一个电影本身由一对整数 $$$a_i$$$、$$$b_i$$$ ($$$1 \le a_i \le b_i \le 10^9$$$) 描述 - 第 $$$i$$$ 电影的第一个和最后一个播出天。
保证输入中所有测试用例的值 $$$n$$$ 的总和不超过 $$$2 \cdot 10^5$$$。
输出
按照给定测试用例在输入中出现的顺序打印 $$$t$$$ 答案:第 $$$i$$$ 答案应由两行组成。在每个测试用例答案的第一行打印整数 $$$d$$$:
- $$$d=0$$$,如果有一个时间表,所有电影都在播出期间观看,
- $$$d>0$$$,如果这样的时间表不存在——在这种情况下,$$$d$$$等于播出结束后所有观看“延迟”中的最大值中的最小值。
在每个测试用例答案的第二行中,打印 $$$n$$$ 正整数 $$$t_1, t_2, \dots, t_n$$$,其中 $$$t_i$$$ 是 Polycarp 需要在最佳时间表中观看第 $$$i$$$ 部电影的日期。
如果有多个答案,请打印其中任何一个。
示例
输入 #1
3 7 2 1 2 1 3 2 2 2 3 1 1 2 3 1 2 5 3 1 1 1 1 1 1 1 1 1 1 6 1 13 13 31 31 25 25 12 12 14 14 10 10
输出 #1
1 1 3 2 3 1 4 2 1 1 1 1 2 2 0 13 31 25 12 14 10