A13203 | Falling Blocks

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.

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

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$ .