F - 我讨厌最短路径问题

评分：600 分

问题描述

有一个由 $H+1$ 行和 $W$ 列的方格网格。

你将从顶部的某个方格开始，重复向右或向下移动一个方格。然而，对于 $1$ 到 $H$ 之间的每个整数 $i$，你不能从第 $i$ 行中的第 $A_i$、$(A_i + 1)$、$\ldots$、 $B_i$ 列的方格向下移动。

对于从顶部的任何一个方格开始，找到到达第 $(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$ 个测试的答案。

示例

输入示例 1

4 4
2 4
1 1
2 3
2 4

输出示例 1

1
3
6
-1

令 $(i,j)$ 表示位于从上而下的第 $i$ 行和从左到右的第 $j$ 列的方格。

对于 $k=1$，我们需要进行一步移动，如 $(1,1)$ → $(2,1)$。

对于 $k=2$，我们需要进行三步移动，如 $(1,1)$ → $(2,1)$ → $(2,2)$ → $(3,2)$。

对于 $k=3$，我们需要进行六步移动，如 $(1,1)$ → $(2,1)$ → $(2,2)$ → $(3,2)$ → $(3,3)$ → $(3,4)$ → $(4,4)$。

对于 $k=4$，无法到达第五行任何一个方格。