T821313 公告展示（display）

题目描述

学校的电子公告屏最多同时展示三条公告。管理员会在一段长为 $K$ 秒的发布时段内，依次发布 $N$ 条公告。公告按发布时间从早到晚编号为 $1,2,\ldots,N$，第 $i$ 条公告在时刻 $t_i$ 发布，展示资格持续 $d_i$ 秒。

一条公告从发布时刻开始有效，在时刻 $t_i+d_i$ 到期。也就是说，它仅在 $t_i\le t<t_i+d_i$ 时有效；若 $d_i=0$，它不会被展示。

在任意时刻，公告屏按照下面的规则选择展示内容：

• 若当前有效的公告不超过三条，则全部展示。
• 否则，只展示当前有效的公告中，发布时间最晚的三条。

没有被选中的公告只是暂时不在屏幕上显示，其到期时刻不会改变。如果较新的公告到期，较旧但仍然有效的公告可能重新出现。

从时刻 $K$ 开始，管理员不再发布新公告，但已经发布的公告仍按照上述规则展示，直到全部到期。

请计算每条公告累计在屏幕上显示了多少秒。

输入格式

第一行包含一个整数 $T$，表示测试数据的组数。

对于每组测试数据：

第一行包含一个整数 $N$，第二行包含一个整数 $K$。

接下来 $N$ 行，第 $i$ 行包含两个整数 $t_i,d_i$，分别表示第 $i$ 条公告的发布时间和展示资格持续时间。

输出格式

对于每组测试数据，输出 $N$ 行。第 $i$ 行输出一个整数，表示第 $i$ 条公告累计显示的秒数。各组输出之间不需要空行。

输入输出样例 #1

输入 #1

1
7
300
0 120
35 120
70 120
110 120
140 120
150 120
210 120

输出 #1

110
105
80
100
120
120
120

说明/提示

第 $1$ 条公告从时刻 $0$ 开始显示。时刻 $110$，第 $4$ 条公告发布，最新的三条有效公告变为第 $2,3,4$ 条，第 $1$ 条不再显示，因此它累计显示 $110$ 秒。

第 $2,3,4$ 条公告分别在时刻 $140,150,210$ 被更新的三条有效公告遮挡，累计显示时间分别为 $140-35=105$、$150-70=80$、$210-110=100$ 秒。

第 $5,6,7$ 条公告均从发布一直显示到自身到期，因此各显示 $120$ 秒。第 $7$ 条公告在时刻 $330$ 才到期，晚于发布时段结束的时刻 $300$。

样例 2

见 考生目录/display/display2.in 与 考生目录/display/display2.ans。该样例满足测试点 $1\sim3$ 的约束。

样例 3

见 考生目录/display/display3.in 与 考生目录/display/display3.ans。该样例满足测试点 $4\sim6$ 的约束。

样例 4

见 考生目录/display/display4.in 与 考生目录/display/display4.ans。该样例满足测试点 $7\sim10$ 的约束。

样例 5

见 考生目录/display/display5.in 与 考生目录/display/display5.ans。该样例满足测试点 $11\sim15$ 的约束。

样例 6

见 考生目录/display/display6.in 与 考生目录/display/display6.ans。该样例满足测试点 $16\sim20$ 的约束。

样例 7

见 考生目录/display/display7.in 与 考生目录/display/display7.ans。该样例满足测试点 $16\sim20$ 的约束。

数据范围

对于所有数据，保证：

• $1\le T\le10$；
• 每组数据中，$1\le N\le200000$，$N\le K\le10^9$；
• 每组数据中，$0\le t_1<t_2<\cdots<t_N<K$；
• $d_i\in\{0,120,300,600,1800,3600,7200,10800,14400,18000\}$；
• 同一输入文件中，所有数据的 $N$ 之和不超过 $800000$；
• 所有输入均为整数。