Problem Description

JOI is passionate about collecting cards in a card game. Each card in the game has two integers representing its strength and cost. To obtain a new card, JOI brings $N$ cards to a card exchange. The cards are numbered from $1$ to $N$. For the $i$-th card ($1 \leq i \leq N$), its strength is $S_i$ and its cost is $V_i$.

There are two machines available at the exchange. If you insert two cards $A$ and $B$ into one of the machines, you can obtain a card $C$ that satisfies the following:

• If you use the first machine, then the strength of $C$ is the maximum of the strengths of $A$ and $B$, and the cost of $C$ is the maximum of the costs of $A$ and $B$.
• If you use the second machine, then the strength of $C$ is the minimum of the strengths of $A$ and $B$, and the cost of $C$ is the minimum of the costs of $A$ and $B$.

JOI plans to use these machines exactly $N - 1$ times to obtain one new card. To do this, he arranges the $N$ cards in order from card $1$ to card $N$. Then, he repeats the following operation $N - 1$ times:

• Choose two adjacent cards, use one of the machines to obtain a new card, and place the new card at the position of the two chosen cards before the operation.

After performing $N - 1$ operations, JOI will have only one card left. The strength and cost of this card depend on the operations he performs.

JOI has a list of cards that he hopes to obtain after performing $N - 1$ operations. The $j$-th card ($1 \leq j \leq M$) is represented by a pair of integers $(T_j, W_j)$, where $T_j$ is its strength and $W_j$ is its cost. Write a program that, given information about JOI's cards and the list of cards he wants, determines which cards in the list he can obtain after performing $N - 1$ operations.

Input Format

Read the following data from standard input.

• $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$

Output Format

Write one line to standard output. The output should contain, in increasing order, the indices of all cards in the list that JOI can obtain after performing $N - 1$ operations.

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

Hint

Sample Explanation 1

For example, JOI can obtain a card with strength 2 and cost 3 in the following way:

• Trade in card 4 and card 5 to obtain a card with strength 1 and cost 1.
• Trade in card 3 and the card obtained in the first operation to obtain a card with strength 1 and cost 1.
• Trade in card 1 and card 2 to obtain a card with strength 2 and cost 3.
• Trade in the cards obtained in the second and third operations to obtain a card with strength 2 and cost 3.

Note that even if a card with strength 2 and cost 3 is obtained in the third operation, JOI still needs to perform the last operation. Even if a certain card is obtained after some operations, it may still be impossible to obtain it after performing all $N - 1$ operations.

The sample input satisfies the constraints of all subtasks.

Sample Explanation 2

As in this sample output, if it is impossible to obtain any card in the list after performing $N - 1$ operations, output an empty line.

The sample input satisfies the constraints of all subtasks.

Sample Explanation 3

The sample input satisfies the constraints of all subtasks.

Constraints

• $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$).
• All given values are integers.

Subtasks

1. (11 points) $N \leq 20$, $M \leq 10$.
2. (38 points) $N \leq 2,000$, $M \leq 10$.
3. (22 points) $M \leq 10$.
4. (29 points) No additional constraints.

Translated by ChatGPT 5