题目描述

JOI 君对一款卡牌游戏中的卡牌收集充满热情。卡牌游戏中的每张卡牌都有两个整数，代表其强度和成本。为了获得一张新卡牌，JOI 君将 $N$ 张卡牌带到一个卡牌交换处。每张卡牌编号从 $1$ 到 $N$。第 $i$ 张卡牌（$1 \leq i \leq N$）的强度是 $S_i$，成本是 $V_i$。

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

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

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

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

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

JOI 君有一个希望在执行 $N-1$ 次操作后获得的卡牌列表。第 $j$ 张卡牌（$1 \leq j \leq M$）由一对整数 $(T_j, W_j)$ 表示，其中 $T_j$ 是第 $j$ 张卡牌的强度，$W_j$ 是第 $j$ 张卡牌的成本。编写一个程序，给定有关 JOI 君卡牌的信息以及他想获得的卡牌列表，确定在执行 $N-1$ 次操作后他可以获得的列表中的哪些卡牌。

输入格式

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

• $N$ $M$
• $S_1$ $V_1$
• $S_2$ $V_2$
• ...
• $S_N$ $V_N$
• $T_1$ $W_1$
• $T_2$ $W_2$
• ...
• $T_M$ $W_M$

输出格式

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

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

1 3

2 2
1 1
2 2
1 2
2 1

8 8
5 2
4 4
1 3
7 8
3 1
8 7
6 5
2 6
1 4
7 2
8 8
3 1
5 6
2 7
6 3
2 5

3 4 5 8

提示

样例解释 1

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

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

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

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

样例解释 2

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

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

样例解释 3

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

约束条件

• $2 \leq N \leq 200,000$．
• $1 \leq M \leq 200,000$．
• $1 \leq S_i \leq 10^9$ ($1 \leq i \leq N$)．
• $1 \leq V_i \leq 10^9$ ($1 \leq i \leq N$)．
• $1 \leq T_j \leq 10^9$ ($1 \leq j \leq M$)．
• $1 \leq W_j \leq 10^9$ ($1 \leq j \leq M$)．
• 给定的值均为整数。

子任务

1. (11 分) $N \leq 20$，$M \leq 10$．
2. (38 分) $N \leq 2,000$，$M \leq 10$．
3. (22 分) $M \leq 10$．
4. (29 分) 无额外约束。