{"raw_statement":[{"iden":"statement","content":"JOI 君对一款卡牌游戏中的卡牌收集充满热情。卡牌游戏中的每张卡牌都有两个整数，代表其强度和成本。为了获得一张新卡牌，JOI 君将 $N$ 张卡牌带到一个卡牌交换处。每张卡牌编号从 $1$ 到 $N$。第 $i$ 张卡牌（$1 \\leq i \\leq N$）的强度是 $S_i$，成本是 $V_i$。\n\n卡牌交换处有两台机器可供使用。如果你将两张卡牌 $A$ 和 $B$ 插入其中一台机器，你将能够获得满足以下条件的卡牌 $C$：\n\n- 如果你使用第一台机器，那么 $C$ 的强度等于 $A$ 和 $B$ 的强度中的最大值，并且 $C$ 的成本等于 $A$ 和 $B$ 的成本中的最大值。\n- 如果你使用第二台机器，那么 $C$ 的强度等于 $A$ 和 $B$ 的强度中的最小值，并且 $C$ 的成本等于 $A$ 和 $B$ 的成本中的最小值。\n\nJOI 君计划使用这些机器正好 $N - 1$ 次以获得一张新卡牌。为此，他将 $N$ 张卡牌按卡牌 $1$ 到卡牌 $N$ 的顺序依次排列。然后，他重复以下操作 $N - 1$ 次：\n\n- 选择两张相邻的卡牌，使用其中一台机器来得到一张新卡牌，并将新卡牌放在操作前所选两张卡牌的位置。\n\n在执行 $N-1$ 次操作后，JOI 君将只剩下一张卡牌。这张卡牌的强度和成本将取决于他执行的操作。\n\nJOI 君有一个希望在执行 $N-1$ 次操作后获得的卡牌列表。第 $j$ 张卡牌（$1 \\leq j \\leq M$）由一对整数 $(T_j, W_j)$ 表示，其中 $T_j$ 是第 $j$ 张卡牌的强度，$W_j$ 是第 $j$ 张卡牌的成本。编写一个程序，给定有关 JOI 君卡牌的信息以及他想获得的卡牌列表，确定在执行 $N-1$ 次操作后他可以获得的列表中的哪些卡牌。\n"},{"iden":"input","content":"从标准输入读取以下数据。\n\n- $N$ $M$\n- $S_1$ $V_1$\n- $S_2$ $V_2$\n- ...\n- $S_N$ $V_N$\n- $T_1$ $W_1$\n- $T_2$ $W_2$\n- ...\n- $T_M$ $W_M$"},{"iden":"output","content":"向标准输出写入一行，输出应按升序包含 JOI 君可以在执行 $N-1$ 次操作后获得的列表中所有卡牌的编号。\n"},{"iden":"note","content":"#### 样例解释 1\n\n例如，JOI 君可以通过以下方式获得一张强度为 2，成本为 3 的卡牌：\n\n- 交出卡牌 4 和卡牌 5，获得一张强度为 1，成本为 1 的卡牌。\n- 交出卡牌 3 和第一次操作中获得的卡牌，获得一张强度为 1，成本为 1 的卡牌。\n- 交出卡牌 1 和卡牌 2，获得一张强度为 2，成本为 3 的卡牌。\n- 交出第二次和第三次操作中获得的卡牌，获得一张强度为 2，成本为 3 的卡牌。\n\n请注意，即使在第三次操作中获得了一张强度为 2，成本为 3 的卡牌，JOI 君仍需要执行最后一次操作。即使在某些操作后获得了某张卡牌，也可能在执行 $N-1$ 次操作后无法获得它。\n\n这个样例输入满足所有子任务的约束条件。\n\n#### 样例解释 2\n\n与此样例输出一样，如果在执行 $N-1$ 次操作后无法获得列表中的任何卡牌，则应输出一个空行。\n\n这个样例输入满足所有子任务的约束条件。\n\n#### 样例解释 3\n\n这个样例输入满足所有子任务的约束条件。\n\n\n### 约束条件\n\n- $2 \\leq N \\leq 200,000$．\n- $1 \\leq M \\leq 200,000$．\n- $1 \\leq S_i \\leq 10^9$ ($1 \\leq i \\leq N$)．\n- $1 \\leq V_i \\leq 10^9$ ($1 \\leq i \\leq N$)．\n- $1 \\leq T_j \\leq 10^9$ ($1 \\leq j \\leq M$)．\n- $1 \\leq W_j \\leq 10^9$ ($1 \\leq j \\leq M$)．\n- 给定的值均为整数。\n\n### 子任务\n\n1. (11 分) $N \\leq 20$，$M \\leq 10$．\n2. (38 分) $N \\leq 2,000$，$M \\leq 10$．\n3. (22 分) $M \\leq 10$．\n4. (29 分) 无额外约束。"}],"translated_statement":null,"sample_group":[["5 3\n1 3\n2 2\n4 4\n1 3\n1 1\n2 3\n2 1\n4 4","1 3"],["2 2\n1 1\n2 2\n1 2\n2 1\n",""],["8 8\n5 2\n4 4\n1 3\n7 8\n3 1\n8 7\n6 5\n2 6\n1 4\n7 2\n8 8\n3 1\n5 6\n2 7\n6 3\n2 5","3 4 5 8"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}