CF1297I.Falling Blocks

Recently, Polycarp has invented a new mobile game with falling blocks.

In the game, $n$ blocks are falling down, one at a time, towards a flat surface with length $d$ units. Each block can be represented as a rectangle with coordinates from $l_i$ to $r_i$ and unit height, dropped downwards from very high up. A block falls until it comes in contact with the flat surface or any other block. Let's define that block $a$ covers block $b$ if $l_a \le l_b \le r_b \le r_a$.

Consider what happens when a new block $i$ falls. If the new (upper) block $i$ comes in contact with any block $j$ such that block $i$ does not cover block $j$, block $i$ will stick to block $j$, and no blocks will disappear. Otherwise, all blocks that block $i$ covers and is in contact with will be vaporized, and block $i$ will continue falling with the ability to vaporize lower blocks.

For example, consider what happens when three blocks $(1,2)$, $(2,3)$ and $(1,3)$ fall, in that order. The first block will stick to the flat surface. Then, the second block will stick to the first block. Finally, the third block will vaporize the second block, keep falling, vaporize the first block, and stick to the flat surface.

Here is a graphic for the first example.

After each block falls, help Polycarp determine how many blocks will remain!

最近，Polycarp 发明了一款全新的下落方块类手机游戏。

游戏中，共有 $n$ 个方块依次从高处垂直下落，目标是一个长度为 $d$ 单位的水平平面。每个方块可表示为一个矩形，其横坐标范围为 $l_i$ 到 $r_i$、高度为 1 个单位，自极高处垂直下落。方块持续下落，直至接触到水平平面或其他已存在的方块。我们定义：若方块 $a$ 满足 $l_a \le l_b \le r_b \le r_a$，则称方块 $a$ 覆盖方块 $b$。

考虑第 $i$ 个新方块下落时的情形：

• 若该新（上方）方块 $i$ 在下落过程中首次接触某个方块 $j$，且方块 $i$ 并未覆盖方块 $j$，则方块 $i$ 将粘附在方块 $j$ 上，且所有已有方块均保持不变；
• 否则（即方块 $i$ 接触到的所有方块 $j$ 均被其覆盖），所有被方块 $i$ 覆盖且与其直接接触的方块将被瞬间汽化，而方块 $i$ 将继续下落，并保有汽化更下方方块的能力。

例如，考虑三个方块 $(1,2)$、$(2,3)$ 和 $(1,3)$ 按此顺序下落的情形：

• 第一个方块将粘附在水平平面上；
• 第二个方块将粘附在第一个方块上；
• 第三个方块将汽化第二个方块，继续下落，再汽化第一个方块，最终粘附在水平平面上。

此图为第一个示例的示意图。

请在每个方块下落完毕后，帮 Polycarp 计算当前剩余的方块数量！

The first line contains two integers $n$ and $d$ ($1 \le n, d \le 10^5$) — the number of falling blocks and the length of the flat surface.

The $i$-th of the following $n$ lines contains integers $l_i$ and $r_i$ ($1 \le l_i \le r_i \le d$) — the coordinates of the $i$-th block.

第一行包含两个整数 $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$ 个方块的坐标。

Output $n$ integers. The $i$-th integer should be the number of blocks that will be left after the $i$-th block falls.

输出 $n$ 个整数。其中第 $i$ 个整数应为第 $i$ 个方块下落结束后剩余的方块数量。

The first example is explained above.

In the second example, this is what happens after each block falls:

• Block $1$ will stick to the flat surface.
• Block $2$ will stick to the flat surface.
• Block $3$ will stick to blocks $1$ and $2$. Note that block $3$ will not vaporize block $2$ because it does not cover block $1$ and is in contact with it.
• Block $4$ will vaporize all the blocks and stick to the flat surface.
• Block $5$ will stick to block $4$
• Block $6$ will stick to block $5$.
• Block $7$ will stick to block $6$. Note that no blocks are vaporized because although block $7$ covers block $4$ and block $5$, they never come in contact.
• Block $8$ vaporizes block $7$ and sticks to block $6$.

第一个示例已在上文解释。

在第二个示例中，每个方块下落后发生的情况如下：

• 方块 $1$ 将附着在平坦表面上。
• 方块 $2$ 将附着在平坦表面上。
• 方块 $3$ 将同时附着在方块 $1$ 和方块 $2$ 上。注意：方块 $3$ 不会汽化方块 $2$，因为它未覆盖方块 $1$，且与方块 $1$ 相接触。
• 方块 $4$ 将汽化所有已有方块，并附着在平坦表面上。
• 方块 $5$ 将附着在方块 $4$ 上。
• 方块 $6$ 将附着在方块 $5$ 上。
• 方块 $7$ 将附着在方块 $6$ 上。注意：没有方块被汽化，因为尽管方块 $7$ 覆盖了方块 $4$ 和方块 $5$，但它们从未相互接触。
• 方块 $8$ 将汽化方块 $7$，并附着在方块 $6$ 上。