UOJ Logo Universal Online Judge

UOJ

#877. 【JOISC2024】卡牌收集

附件下载 统计

JOI 君对一款卡牌游戏中的卡牌收集充满热情。卡牌游戏中的每张卡牌都有两个整数,代表其强度和成本。为了获得一张新卡牌,JOI 君将 N 张卡牌带到一个卡牌交换处。每张卡牌编号从 1N。第 i 张卡牌(1iN)的强度是 Si,成本是 Vi

卡牌交换处有两台机器可供使用。如果你将两张卡牌 AB 插入其中一台机器,你将能够获得满足以下条件的卡牌 C

  • 如果你使用第一台机器,那么 C 的强度等于 AB 的强度中的最大值,并且 C 的成本等于 AB 的成本中的最大值。
  • 如果你使用第二台机器,那么 C 的强度等于 AB 的强度中的最小值,并且 C 的成本等于 AB 的成本中的最小值。

JOI 君计划使用这些机器正好 N1 次以获得一张新卡牌。为此,他将 N 张卡牌按卡牌 1 到卡牌 N 的顺序依次排列。然后,他重复以下操作 N1 次:

  • 选择两张相邻的卡牌,使用其中一台机器来得到一张新卡牌,并将新卡牌放在操作前所选两张卡牌的位置。

在执行 N1 次操作后,JOI 君将只剩下一张卡牌。这张卡牌的强度和成本将取决于他执行的操作。

JOI 君有一个希望在执行 N1 次操作后获得的卡牌列表。第 j 张卡牌(1jM)由一对整数 (Tj,Wj) 表示,其中 Tj 是第 j 张卡牌的强度,Wj 是第 j 张卡牌的成本。编写一个程序,给定有关 JOI 君卡牌的信息以及他想获得的卡牌列表,确定在执行 N1 次操作后他可以获得的列表中的哪些卡牌。

输入格式

从标准输入读取以下数据。

  • N M
  • S1 V1
  • S2 V2
  • ...
  • SN VN
  • T1 W1
  • T2 W2
  • ...
  • TM WM

输出格式

向标准输出写入一行,输出应按升序包含 JOI 君可以在执行 N1 次操作后获得的列表中所有卡牌的编号。

样例解释 1

例如,JOI 君可以通过以下方式获得一张强度为 2,成本为 3 的卡牌:

  • 交出卡牌 4 和卡牌 5,获得一张强度为 1,成本为 1 的卡牌。
  • 交出卡牌 3 和第一次操作中获得的卡牌,获得一张强度为 1,成本为 1 的卡牌。
  • 交出卡牌 1 和卡牌 2,获得一张强度为 2,成本为 3 的卡牌。
  • 交出第二次和第三次操作中获得的卡牌,获得一张强度为 2,成本为 3 的卡牌。

请注意,即使在第三次操作中获得了一张强度为 2,成本为 3 的卡牌,JOI 君仍需要执行最后一次操作。即使在某些操作后获得了某张卡牌,也可能在执行 N1 次操作后无法获得它。

这个样例输入满足所有子任务的约束条件。

样例解释 2

与此样例输出一样,如果在执行 N1 次操作后无法获得列表中的任何卡牌,则应输出一个空行。

这个样例输入满足所有子任务的约束条件。

样例解释 3

这个样例输入满足所有子任务的约束条件。

约束条件

  • 2N200,000
  • 1M200,000
  • 1Si109 (1iN).
  • 1Vi109 (1iN).
  • 1Tj109 (1jM).
  • 1Wj109 (1jM).
  • 给定的值均为整数。

子任务

  1. (11 分) N20M10
  2. (38 分) N2,000M10
  3. (22 分) M10
  4. (29 分) 无额外约束。