题目描述

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

你从顶部某一行的一个方格开始，每次只能向右或向下移动一个方格。然而，对于从上到下的第 $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$ $\ldots$ $A_H$ $B_H$

输出

输出共 $H$ 行。第 $i$ 行应包含第 $k=i$ 个案例的答案。

示例输入 1

4 4
2 4
1 1
2 3
3 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$，无法到达从顶部往下数第五行的任何方格。