← 返回题目列表

AtCoder · abc177_f

F. 我讨厌最短路径问题

中文机器翻译题面 查看原题

分数: 600 点

问题陈述

有一个正方形网格, H+1 水平行和 W 垂直列。

您将从顶行的一个方格开始,然后重复向右或向下移动一个方格。然而,对于每个整数 i 来自 1 通过 H,您无法从 A_i-th, (A_i + 1)-th, \ldots, B_i从左边开始第一个方格 i从顶部算起的第 3 行。

对于每个整数 k 来自 1 通过 H,找到到达其中一个方格所需的最小移动次数 (k+1)从顶部算起的第 3 行。 (可以针对每种情况单独选择起始方格。)如果从顶行中的任何方格开始, (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,不可能到达从上往下数第五行的任何方格。