You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

问题描述

有一个 $H+1$ 行 $W$ 列的矩阵，你每步可以在矩阵中向右或向下移动一个格子。

但是在第 𝑖 $(1\le i \le H)$行中， 你无法 第 $A_i$ 至 $B_i$ 列的格子向下走。

对于每一个 $k,(1\le k \le H)$，求出从第 1 行的任意一个格子出发移动到第 $k+1$ 行的最少步数，若无法移动到第$k+1$行则输出 -1。

输入格式

第一行两个整数 $H$ 和 $W$，

接下来 $H$ 行每行两个整数 $A_i$ 和 $B_i$。

输出格式

共 $H$ 行，每行一个整数。

输入1

4 4
2 4
1 1
2 3
2 4

输出1

1
3
6
-1

解释1

𝑘=1 时，其中一种答案最小的移动顺序为 (1,1)→(2,1)；

𝑘=2 时，一种移动顺序为 (1,1)→(2,1)→(2,2)→(3,2)；

𝑘=3 时，一种移动顺序为 (1,1)→(2,1)→(2,2)→(3,2)→(3,3)→(3,4)→(4,4)

𝑘=4 时，无法从第 1 行移动到第 5 行。

数据范围

$1 \le H, W \le 2*10^5; 1\le A_i \le B_i \le W$