最近,Polycarp发明了一款新的方块掉落手机游戏。
在游戏中,$$$n$$$ 块一次一个掉落,落向长度为 $$$d$$$ 单位的平坦表面。每个块可以表示为一个矩形,其坐标从 $$$l_i$$$ 到 $$$r_i$$$ 以及单位高度,从非常高的地方向下下降。一个方块会下落,直到它接触到平坦的表面或任何其他方块。让我们定义块 $$$a$$$ 覆盖块 $$$b$$$ 如果 $$$l_a \le l_b \le r_b \le r_a$$$。
考虑当一个新区块 $$$i$$$ 掉落时会发生什么。如果新的(上)块 $$$i$$$ 与任何块 $$$j$$$ 接触,使得块 $$$i$$$ 不覆盖块 $$$j$$$,块 $$$i$$$ 将粘在块 $$$j$$$ 上,并且没有块会消失。否则,所有覆盖并接触方块 $$$i$$$ 的方块都将被蒸发,并且方块 $$$i$$$ 将继续下落,并具有蒸发较低方块的能力。
例如,考虑当三个块 $$$(1,2)$$$、$$$(2,3)$$$ 和 $$$(1,3)$$$ 按顺序掉落时会发生什么。第一个块将粘在平坦的表面上。然后,第二个块将粘在第一个块上。最后,第三块将蒸发第二块,继续下落,蒸发第一块,并粘在平坦的表面上。
这是第一个示例的图形。
每个方块掉落后,帮助坡旅甲确定还剩下多少方块!
输入
第一行包含两个整数 $$$n$$$ 和 $$$d$$$ ($$$1 \le n, d \le 10^5$$$) — 下落方块的数量和平坦表面的长度。
以下 $$$n$$$ 行中的第 $$$i$$$ 行包含整数 $$$l_i$$$ 和 $$$r_i$$$ ($$$1 \le l_i \le r_i \le d$$$) — 第 $$$i$$$ 块的坐标。
输出
输出 $$$n$$$ 个整数。第 $$$i$$$ 个整数应该是第 $$$i$$$ 个块掉落后剩余的块数。
示例
输入 #1
3 3 1 2 2 3 1 3
输出 #1
1 2 1
输入 #2
8 6 1 2 3 3 2 3 1 3 2 4 3 6 1 5 1 5
输出 #2
1 2 3 1 2 3 4 4
注意
上面解释了第一个示例。
在第二个示例中,这是每个块掉落后发生的情况:
- 方块 $$$1$$$ 将粘在平坦的表面上。
- 方块 $$$2$$$ 将粘在平坦的表面上。
- 块 $$$3$$$ 将粘在块 $$$1$$$ 和 $$$2$$$ 上。请注意,块 $$$3$$$ 不会蒸发块 $$$2$$$,因为它不覆盖块 $$$1$$$ 并且与其接触。
- 方块 $$$4$$$ 会蒸发所有方块并粘在平坦的表面上。
- 区块 $$$5$$$ 将粘在区块 $$$4$$$ 上
- 区块 $$$6$$$ 将粘在区块 $$$5$$$ 上。
- 区块 $$$7$$$ 将粘在区块 $$$6$$$ 上。请注意,没有任何块被蒸发,因为尽管块 $$$7$$$ 覆盖了块 $$$4$$$ 和块 $$$5$$$,但它们从未接触过。
- 方块 $$$8$$$ 会蒸发方块 $$$7$$$ 并粘在方块 $$$6$$$ 上。