题目描述

在格里达尔王国，有一座通天的魔法高塔，这座高塔共有 $H+1$ 层、$W$ 根螺旋楼梯柱组成。每一层由 $W$ 个房间横向排列，骑士可以在房间之间向右移动，也可以通过楼梯向下进入下一层。

年轻骑士 dash 接受了试炼：从第 $1$ 层的任意房间出发，尝试爬到更高的楼层。但塔中有些通道受到了魔法诅咒，第 $i$ 层中编号从 $A_i$ 到 $B_i$ 的房间中，禁止向下进入下一层。

每一步，dash 只能：

• 在同一层向右移动一格（即房间列数 $+1$）；
• 或向下进入下一层相同列的房间，前提是该房间的楼梯未被诅咒。

你的任务是：对于每一个 $k,(1 \le k \le H)$，判断塞德里克能否从第 $1$ 层出发，最少经过几步，抵达第 $(k+1)$ 层的任意一个房间。若无法到达，输出 -1。

输入格式

第一行两个整数 $H, W$，分别表示楼层数（不含最底层）和每层的房间数。

接下来的 $H$ 行，每行两个整数 $A_i, B_i$，表示第 $i$ 层中，禁止向下走的楼梯列区间是 $[A_i, B_i]$。

输出格式

输出共 $H$ 行，第 $i$ 行的数字表示从第 $1$ 层到达第 $(i+1)$ 层的最少步数，若无法到达，则为 -1。

样例

4 4
2 4
1 1
2 3
2 4

1
3
6
-1

解释 #1

• 第 $2$ 层可由 $(1,1) \rightarrow (2,1)$ 达到
• 第 $3$ 层可由 $(1,1) \rightarrow (2,1) \rightarrow (2,2) \rightarrow (3,2)$
• 第 $4$ 层可由 $(1,1) \rightarrow (2,1) \rightarrow (2,2) \rightarrow (3,2) \rightarrow (3,3) \rightarrow (3,4) \rightarrow (4,4)$
• 第 $5$ 层无法到达

数据范围

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