题目描述

题目译自 JOISC 2024 Day3 T1 「カード収集 / Card Collection」

JOI 君正狂热地收集一个卡牌游戏中的卡牌。游戏中的每张卡牌都有两个整数，表示它的强度和花费。为了得到一张新卡，JOI 君会拿出 $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 君计划使用恰好 $N-1$ 次机器来获得一张新卡。首先，他将这 $N$ 张卡按编号从 $1$ 到 $N$ 的顺序放成一行。然后它进行了如下操作 $N-1$ 次。

• 选择两张相邻的卡，用一台机器将这两张卡换成一张新卡，然后把新卡放在原来两张卡放置的位置。

在 $N-1$ 次操作后，JOI 君会只剩余一张卡。卡的强度和花费取决于他的操作顺序。JOI 君有一张他想在操作 $N-1$ 次后获得的 $M$ 张卡的列表。第 $j$ 张卡用一对整数 $(T_j,W_j)$ 表示，其中 $T_j$ 是强度，$W_j$ 是花费。给定 JOI 君拥有的卡牌信息和他想得到的卡牌信息，写一个程序确定列表中所有的卡是否能在操作 $N-1$ 次后获得。

输入格式

第一行两个整数 $N,M$。

接下来 $N$ 行，每行两个整数 $S_i,V_i$。

接下来 $M$ 行，每行两个整数 $T_j,W_j$。

输出格式

输出一行，表示在 $N-1$ 次操作后 JOI 君能获得的卡牌的下标，按递增顺序输出。

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

1 3

JOI 君可以按如下方式获得强度为 $2$，花费为 $3$ 的卡。

1. 用卡 $4$ 和卡 $5$ 换取一张强度为 $1$，花费为 $1$ 的卡。
2. 用卡 $3$ 和上一次操作获得的卡换取一张强度为 $1$，花费为 $1$ 的卡。
3. 用卡 $1$ 和卡 $2$ 换取一张强度为 $2$，花费为 $3$ 的卡。
4. 用第二和第三次操作得到的卡换取一张强度为 $2$，花费为 $3$ 的卡。

注意即使 JOI 君已经在第三步获得了强度为 $2$，花费为 $3$ 的卡，他也要进行最后一步操作。即使他通过一些步操作可以获得想要的卡，但有可能不能通过 $N-1$ 次操作获得想要的卡。

这组样例满足所有子任务的限制。

2 2
1 1
2 2
1 2
2 1

在这组样例输出中，你需要输出一行空行，因为不可能通过 $N-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

这组样例满足所有子任务的限制。

数据范围与提示

• $2\le N\le 2\times 10^5$
• $1\le M\le 2\times 10^5$
• $1\le S_i,V_i,T_j,W_j\le 10^9$

详细子任务附加限制及分值如下表所示。