問題文

W 個の正方形のマスが左右に並んだ水平な部分があります。最初、すべての部分について、高さは 0 です。ここに高さ 1 の直方体のレンガを N 個、順番に積みます。高さ h の面に接着したレンガの上面の高さは h+1 になります。

i 番目に積むレンガは、左から L_i 番目から R_i 番目のマスをちょうど覆うように置きます。このとき、レンガが覆う範囲の中で最も高い水平な面で接着します。

各レンガについて、上面の高さを求めてください。

制約

• 2 \leq W \leq 5 \times 10^5
• 1 \leq N \leq 2.5 \times 10^5
• 1 \leq L_i \leq R_i \leq W (1 \leq i \leq N)
• 入力はすべて整数

小課題・得点

この問題はいくつかの小課題に分けられ、その小課題のすべてのテストケースに正解した場合に「この小課題に正解した」とみなされます。
提出したソースコードの得点は、正解した小課題の点数の合計となります。

1. (1 点)： W \leq 9000,\ N \leq 9000
2. (1 点)： N \leq 9000
3. (3 点)： 追加の制約はない。

入力例 1

100 4
27 100
8 39
83 97
24 75

出力例 1

1
2
2
3

i 番目に積むレンガをレンガ i と呼びます。
レンガ 1 は、マスの表面に接着するので、上面の高さは 1 です。
レンガ 2 は、レンガ 1 の上面に接着するので、上面の高さは 2 です。
レンガ 3 は、レンガ 1 の上面に接着するので、上面の高さは 2 です。
レンガ 4 は、レンガ 2 の上面に接着するので、上面の高さは 3 です。

入力例 2

3 5
1 2
2 2
2 3
3 3
1 2

出力例 2

1
2
3
4
4

i 番目に積むレンガをレンガ i と呼びます。
レンガ 1 は、マスの表面に接着するので、上面の高さは 1 です。
レンガ 2 は、レンガ 1 の上面に接着するので、上面の高さは 2 です。
レンガ 3 は、レンガ 2 の上面に接着するので、上面の高さは 3 です。
レンガ 4 は、レンガ 3 の上面に接着するので、上面の高さは 4 です。
レンガ 5 は、レンガ 3 の上面に接着するので、上面の高さは 4 です。

入力例 3

10 10
1 3
3 5
5 7
7 9
2 4
4 6
6 8
3 5
5 7
4 6

出力例 3

1
2
3
4
3
4
5
5
6
7

入力例 4

500000 7
1 500000
500000 500000
1 500000
1 1
1 500000
500000 500000
1 500000

出力例 4

1
2
3
4
5
6
7

※この入力例は小課題 2,3 のみの制約を満たします。