4496 - イベント巡り 2 (Event Hopping 2)

IOI Park 将有 n 场活动。

这些活动的编号从 1 到 n。 活动 i 从时间 L_i+10^{-1} 到时间 R_i-10^{-1} 举行。数据保证 L_i 和 R_i 是整数。

JOI 君决定参加其中的 k 个活动。但是，JOI 君不能在中间加入或离开每个活动。在两个活动场所间移动的时间忽略不计。

JOI 君希望参加编号较小的活动。严格来说，JOI 君参加的 k 个活动的编号依次为 a_1,\cdots,a_k，其中 1 \le a_1 < \cdots < a_k \le n。如果序列 (a_1, \cdots, a_k) 的编号小于 (b_1, \cdots, b_k)，当且仅当存在 j\ (1 \le j \le k) 满足在区间 [1,j-1] 里的所有 l 都有 a_l=b_l 和 a_j。

给出每个活动的信息和 JOI 君参加的活动个数 k，判断 JOI 君是否可以参加 k 个活动，如果可以，输出所有的 k 个活动的编号。

输入

第一行，两个正整数 n,k。

第 2 \sim n + 1 行，每行 2 个正整数，L_i, R_i。

输出

如果 JOI 君可以参加 k 个活动：

  • 输出 k 行。
  • 我们设 JOI 君参与的 k 个活动的编号为 a_1, a_2, \cdots, a_k\ (1\le a_1 < \cdots < a_k \le n），你需要在第 j 行输出 a_j\ (1\le j \le k)。 请注意，序列 (a_1, \cdots, a_k) 必须是 最小字典序。

如果 JOI 君无法参加 k 个活动，输出 \texttt{-1}。

样例

输入

5 4
1 3
2 5
8 9
6 8
10 15

输出

1
3
4
5

输入

4 3
1 4
3 5
4 9
7 10

输出

-1

输入

10 6
77412002 93858605
244306432 318243514
280338037 358494212
439397354 492065507
485779890 529132783
571714810 632053254
659767854 709114867
718405631 733610573
786950301 815106357
878719468 899999649

输出

1
2
4
6
7
8

提示

样例 #1 解释

有 2 种方式可以参加正好 4 个活动。

  • 参加 1, 3, 4, 5；
  • 参加 2, 3, 4, 5。

数列 (1,3,4,5) 比数列 (2, 3, 4, 5) 字典序小，所以输出 1, 3, 4, 5。

样例 #2 解释

无论怎么选择都不可能正好参加 3 个活动，所以输出 \tt -1。

对于 100\% 的数据：

  • 1\le n\le 10^5；
  • 1 \le k \le n；
  • 1\le L_i < R_i \le 10^9 (1\le i \le n)。

来源

JOISC

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题