障碍物

题目描述

有一个纵 $H+1$ 格、横 $W$ 格的棋盘。

你从最上面一行的任意一格出发,反复向右或向下移动一格。但是,对于 $1$ 以上 $H$ 以下的每个整数 $i$,从棋盘自上而下第 $i$ 行的左起第 $A_i$ 格、第 $A_i + 1$ 格、$\ldots$、第 $B_i$ 格这些格子,不能向下移动。

对于 $1$ 以上 $H$ 以下的每个整数 $k$,求移动到自上而下第 $k+1$ 行的任意一格所需的最小移动次数。(出发的格子可以在每种情况下分别选择。) 如果从最上面一行任意一格出发都无法移动到第 $k+1$ 行的任何一格,则输出 -1。

输入格式

输入按以下格式从标准输入给出:

$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$ 行格子的方法。

数据范围

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