JOI-kun 热衷于收集卡牌游戏中的卡牌。游戏中的每张卡牌都有两个整数，分别代表其力量和费用。为了获得一张新卡牌，JOI-kun 携带 $N$ 张卡牌前往卡牌交换处。每张卡牌的编号从 $1$ 到 $N$。第 $i$ 张卡牌（$1 \le i \le N$）的力量为 $S_i$，费用为 $V_i$。

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

• 如果你使用第一台机器，那么 C 的力量必须等于 A 和 B 力量的最大值，且 C 的费用必须等于 A 和 B 费用的最大值。
• 如果你使用第二台机器，那么 C 的力量必须等于 A 和 B 力量的最小值，且 C 的费用必须等于 A 和 B 费用的最小值。

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

选择两张相邻的卡牌，使用其中一台机器将它们交换为一张新卡牌，并将新卡牌放置在操作前这两张卡牌所在的位置。

在执行 $N - 1$ 次操作后，JOI-kun 将只剩下一张卡牌。这张卡牌的力量和费用取决于他所执行的操作。JOI-kun 有一个他希望在执行 $N - 1$ 次操作后获得的卡牌列表。第 $j$ 张卡牌（$1 \le j \le M$）由一对整数 $(T_j, W_j)$ 表示，其中 $T_j$ 是该卡牌的力量，$W_j$ 是该卡牌的费用。编写一个程序，在给定 JOI-kun 的卡牌信息以及他希望获得的卡牌列表的情况下，确定列表中他可以在执行 $N - 1$ 次操作后获得的所有卡牌。

输入格式

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

$N \ M$ $S_1 \ V_1$ $S_2 \ V_2$ $\vdots$ $S_N \ V_N$ $T_1 \ W_1$ $T_2 \ W_2$ $\vdots$ $T_M \ W_M$

输出格式

输出一行到标准输出。输出应包含 JOI-kun 在执行 $N - 1$ 次操作后可以获得的列表中所有卡牌的索引，按升序排列。如果无法获得列表中的任何卡牌，则输出一个空行。

数据范围

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

子任务

1. (11 分) $N \le 20$，$M \le 10$。
2. (38 分) $N \le 2\,000$，$M \le 10$。
3. (22 分) $M \le 10$。
4. (29 分) 无附加限制。

样例

样例输入 1

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

样例输出 1

1 3

说明

例如，JOI-kun 可以通过以下方式获得一张力量为 2、费用为 3 的卡牌：

1. 将第 4 张卡牌和第 5 张卡牌交换为一张力量为 1、费用为 1 的卡牌。
2. 将第 3 张卡牌和第一次操作中获得的卡牌交换为一张力量为 1、费用为 1 的卡牌。
3. 将第 1 张卡牌和第 2 张卡牌交换为一张力量为 2、费用为 3 的卡牌。
4. 将第二次和第三次操作中获得的卡牌交换为一张力量为 2、费用为 3 的卡牌。

注意，即使 JOI-kun 在第三次操作中获得了力量为 2、费用为 3 的卡牌，他也必须执行最后一次操作。即使在经过若干次操作后获得了某张卡牌，在执行 $N - 1$ 次操作后也未必能获得它。

样例输入 2

2 2
1 1
2 2
1 2
2 1

样例输出 2

样例输入 3

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

3 4 5 8