← 返回题目列表

Codeforces · 1297/F

F. 电影迷

中文机器翻译题面 查看原题

最近,波利卡普一直是电影新奇事物的粉丝,并试图不要错过它们!

在不久的将来,将发布$$$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