2024-sp_Card_Collection (JOI JOI_spring)
Time limit: 4 seconds | Memory limit: 1024 MB | Task type: batch
Algorithms: mathematics, bitmask, interval dp, dynamic programming

![](_page_0_Picture_0.jpeg)

# Card Collection

JOI-kun is enthusiastic about collecting cards in a card game. Each card in the card game has two integers representing its strength and cost. To obtain a new card, JOI-kun brings *N* cards to a card exchange. Each card is numbered from 1 to *N*. The strength of card *i* (1 ≤ *i* ≤ *N*) is *S<sub>i</sub>* and the cost of card *i* is *V<sub>i</sub>*.

There are two machines available in the card exchange. If you insert two cards, A and B, into one of the machines, you will be able to receive any card C satisfying the following conditions.

*   If you use the first machine, then the strength of C must be equal to the *maximum* of the strength of A and B, and the cost of C must be equal to the *maximum* of the cost of A and B.
*   If you use the second machine, then the strength of C must be equal to the *minimum* of the strength of A and B, and the cost of C must be equal to the *minimum* of the cost of A and B.

JOI-kun plans to use the machines exactly *N* − 1 times to obtain a new card. To do this, he lines up the *N* cards in a row from card 1 to card *N*. He then repeats the following operation *N* − 1 times.

Choose two adjacent cards, exchange them with a new card using one of the machines, and place the new card where the chosen two cards were in the row before the operation.

After performing *N* − 1 operations, JOI-kun will have only one card left. The strength and cost of this card will depend on the operations he performs. JOI-kun has a list of *M* cards that he wants to obtain after performing *N* − 1 operations. The *j*-th card (1 ≤ *j* ≤ *M*) is represented by a pair of integers (*T<sub>j</sub>*, *W<sub>j</sub>*), where *T<sub>j</sub>* is the strength and *W<sub>j</sub>* is the cost of the *j*-th card. Write a program that, given information about JOI-kun's cards and the list of cards he wants to obtain, determines all the cards in the list that he can obtain after performing *N* − 1 operations.

## Input

The input is given from standard input in the following format:

```
N M
S1 V1
S2 V2
...
SN VN
T1 W1
T2 W2
...
TM WM
```

## Output

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

## Constraints

*   2 ≤ *N* ≤ 200 000.
*   1 ≤ *M* ≤ 200 000.
*   1 ≤ *S<sub>i</sub>* ≤ 10<sup>9</sup> (1 ≤ *i* ≤ *N*).
*   1 ≤ *V<sub>i</sub>* ≤ 10<sup>9</sup> (1 ≤ *i* ≤ *N*).
*   1 ≤ *T<sub>j</sub>* ≤ 10<sup>9</sup> (1 ≤ *j* ≤ *M*).
*   1 ≤ *W<sub>j</sub>* ≤ 10<sup>9</sup> (1 ≤ *j* ≤ *M*).
*   Given values are all integers.

## Subtasks

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

## Sample Input and Output

| Sample Input 1 | Sample Output 1 |
| :------------- | :------------- |
| 5 3            | 1 3            |
| 1 3            |                |
| 2 2            |                |
| 4 4            |                |
| 1 3            |                |
| 1 1            |                |
| 2 3            |                |
| 2 1            |                |
| 4 4            |                |

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

1.  Exchange card 4 and card 5 for a card with strength 1 and cost 1.
2.  Exchange card 3 and the card received in the first operation for a card with strength 1 and cost 1.
3.  Exchange card 1 and card 2 for a card with strength 2 and cost 3.
4.  Exchange the cards received in the second and third operations for a card with strength 2 and cost 3.

Note that JOI-kun needs to perform the last operation even if he receives a card with strength 2 and cost 3 in the third operation. Even if he receives a certain card after some number of operations, it may not be possible to obtain it after performing *N* − 1 operations.

This sample input satisfies the constraints of all the subtasks.

| Sample Input 2 | Sample Output 2 |
| :------------- | :------------- |
| 2 2            |                |
| 1 1            |                |
| 2 2            |                |
| 1 2            |                |
| 2 1            |                |

As in this sample output, you should output an empty line if it is impossible to obtain any card in the list after *N* − 1 operations.

This sample input satisfies the constraints of all the subtasks.

| Sample Input 3 | Sample Output 3 |
| :------------- | :------------- |
| 8 8            | 3 4 5 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            |                |

This sample input satisfies the constraints of all the subtasks.

Starter code:

Grader code:

Setup script:

Evaluation script: