配点 : $600$ 点

問題文

縦 $H+1$ マス横 $W$ マスのマス目があります。

あなたは一番上のいずれかのマスから始めて右か下に一マス移動することを繰り返します。ただし、$1$ 以上 $H$ 以下のそれぞれの整数 $i$ について、グリッドの上から $i$ マス目の左から $A_i$ マス目、$A_i + 1$ マス目、$\ldots$、$B_i$ マス目のマスからは下に移動することができません。

$1$ 以上 $H$ 以下のそれぞれの整数 $k$ について、上から $k+1$ マス目のいずれかのマス目まで移動するための最小の移動回数を求めてください。(出発するマスは各場合について個別に選ぶことができます。) 一番上のどのマスから始めても上から $k+1$ マス目のいずれのマス目にも移動できない場合、代わりに -1 を出力してください。

制約

• $1 \leq H,W \leq 2\times 10^5$
• $1 \leq A_i \leq B_i \leq W$

入力

入力は以下の形式で標準入力から与えられる。

$H$ $W$

$A_1$ $B_1$

$A_2$ $B_2$

$:$

$A_H$ $B_H$

出力

$H$ 行出力せよ。$i$ 行目には、$k=i$ のときの答えを出力せよ。

4 4
2 4
1 1
2 3
2 4

1
3
6
-1

上から $i$ マス目、左から $j$ マス目のマスをマス $(i,j)$ とします。

$k=1$ のとき、マス $(1,1)$ → $(2,1)$ のように $1$ 回で移動できます。

$k=2$ のとき、マス $(1,1)$ → $(2,1)$ → $(2,2)$ → $(3,2)$ のように $3$ 回で移動できます。

$k=3$ のとき、マス $(1,1)$ → $(2,1)$ → $(2,2)$ → $(3,2)$ → $(3,3)$ → $(3,4)$ → $(4,4)$ のように $6$ 回で移動できます。

$k=4$ のとき、上から $5$ マス目のマスに移動する方法はありません。