Problem Description

JOI-kun 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-kun brings $N$ cards to a card exchange location. Each card is numbered from $1$ to $N$. The strength of the $i$-th card ($1 \leq i \leq N$) is $S_i$, and its cost is $V_i$.

The card exchange location has two machines available for use. If you insert two cards $A$ and $B$ into one of the machines, you can obtain a card $C$ that meets the following conditions:

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

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

• Select two adjacent cards, use one of the machines to obtain a new card, and place the new card in the position of the two selected cards.

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

JOI-kun has a list of cards 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 the strength of the $j$-th card and $W_j$ is its cost. Write a program that, given information about JOI-kun's cards and the list of cards he wants to obtain, determines which cards from the list he can obtain after performing $N-1$ operations.

Input Format

Read the following data from the 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 the standard output. The output should contain the numbers of all cards from the list that JOI-kun can obtain after performing $N-1$ operations, in ascending order.

Sample Input and Output

Sample Input #1

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

Sample Output #1

1 3

Sample Input #2

2 2
1 1
2 2
1 2
2 1

Sample Output #2

Sample Input #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

Sample Output #3

3 4 5 8

Notes/Hints

Sample Explanation 1

For example, JOI-kun can obtain a card with strength 2 and cost 3 as follows:

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

Note that even if a card is obtained in some operation, it may not be possible to obtain it after performing $N-1$ operations.

This sample input satisfies the constraints for all subtasks.

Sample Explanation 2

As with this sample output, if no cards from the list can be obtained after performing $N-1$ operations, an empty line should be output.

This sample input satisfies the constraints for all subtasks.

Sample Explanation 3

This sample input satisfies the constraints for 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.

见题面 Input 部分

见题面 Output 部分