#P17802. [Ontak2024]REP

[Ontak2024]REP

题目描述

有 nn 个事件,按输入顺序编号 11 到 nn。事件 ii 占用时间区间 [Li,Ri)[L_i,R_i)。

你要选择恰好 kk 个不同事件,使这些区间两两不相交,然后按发生的时间顺序列出所选事件的编号。转移不消耗时间,前一个事件恰好在后一个事件开始时结束是允许的。

在所有长度为 kk 的合法编号序列中,求字典序最小的一个。事件编号不保证与开始或结束时间相关。

给定多个不同或相同的 kk,分别回答。各次查询相互独立。

输入格式

第一行整数 ss,表示该测试所属的最早子任务编号,1≤s≤81\le s\le8。

第二行两个整数 n,qn,q。

接下来 nn 行,第 ii 行两个整数 Li,RiL_i,R_i。

接下来 qq 行,每行一个整数 kk。

输出格式

每次查询输出一行:若无合法方案,输出 -1;否则输出所求的 kk 个事件编号,顺序必须为时间顺序,而非把编号重新排序。

数据范围

  • 1≤n,q≤5000001\le n,q\le500000。
  • 0≤Li<Ri≤10180\le L_i<R_i\le10^{18}。
  • 每个查询满足 1≤k≤n1\le k\le n。
  • 所有查询的 kk 之和不超过 500000500000,包括不可行查询。

样例

输入:

1
6 5
11 13
1 8
6 9
0 5
14 17
4 16
6
2
3
1
4

输出:

-1
1 5
2 1 5
1
4 3 1 5

子任务

编号 附加限制 分值
1 n≤10n\le10 11
2 n≤20n\le20 10
3 n≤500n\le500
4 n≤5000n\le5000 13
5 n≤100000n\le100000 19
6 所有事件持续时间相同 12
7 q=1q=1 15
8 无附加限制 10