oldorhei (EJOI contest)
Time limit: 3 seconds | Memory limit: 256 MB | Task type: batch
Algorithms: geometric transformation, segment tree, range queries

# Old Orhei

Old Orhei (Orheiul Vechi) is a natural and historical complex located on a narrow bend of the Răut River. It consists of *N* archaeological vestiges and *M* one-way roads between some pairs of vestiges. Every road has a unique index between 1 and *M*, defined by the input order in which it is given. Please refer to the *Examples* section for visualizing such a configuration.

Recently an array left by the Cucuteni–Trypillia civilization was discovered by the local scientists. The array consists of *T* integers with values between 1 and *M*. In order to figure out the mystical meaning of this array, the new intern will be instructed to follow this procedure:

At the beginning, the intern starts at some initial archaeological vestige. The other scientists start broadcasting to him a contiguous sub-array of the main array (first broadcasting the first element of the subarray, then the second one, and so on). The intern then changes his location depending on the following rules:

- If the intern can use the road indexed with the current broadcast number (in other words, the intern's current location is equal to the starting point of the corresponding road), the intern traverses it (goes to the end-point of the corresponding road).
- Otherwise the intern does nothing, and remains in his current location.

With the occasion of the 8-th European Junior Olympiad in Informatics, the local scientists have asked you to help them perform the following *Q* queries:

- 1 *L R S* - the scientists want to know what will be the final location of the intern if initially he is located in the *S*-th vestige, and only the contiguous sub-array of the initial array which starts at index *L* and ends at index *R* is broadcasted.
- 2 *i K* - the scientists override the *i*-th element of the array with the value *K*. The change is permanent. (In other words, the array changes so that *A<sub>i</sub>* = *K* after performing the query).

Your task is to answer correctly to all the queries of type 1.

### Input

The first line contains two space-separated integers *N* and *M*, the number of archaeological vestiges and one-way roads.

The next *M* lines contain the description of the roads. In particular, line *i* will contain two space-separated numbers indicating that the *i*-th road starts in *X<sub>i</sub>* and ends in *Y<sub>i</sub>*. There can exist roads for which *X<sub>i</sub>* = *Y<sub>i</sub>* as well as pairs of roads for which *X<sub>i</sub>* = *X<sub>j</sub>*, *Y<sub>i</sub>* = *Y<sub>j</sub>* but *i* ≠ *j*.

The next line contains an integer *T*, the length of the found array.

The next line contains *T* space-separated integers *A<sub>1</sub>*, *A<sub>2</sub>* … *A<sub>T</sub>*, representing the array elements.

The next line contains an integer *Q*, the number of queries.

The next *Q* lines contain the query description:

- 1 *L R S* for a query of type 1.
- 2 *i K* for a query of type 2.

### Output

For each query of type 1 output the answer on a separate line.

### Examples

Note that some of the samples are not valid input for all test groups.

Here is a representation of the first query for the first sample:

Initially, the intern starts in vestige 2, and the sub-array broadcasted is [4, 2, 5].

![](_page_1_Figure_13.jpeg)

The number 4 is broadcasted so the intern moves to vestige 5, since the road with index 4 can be traversed.

![](_page_2_Figure_0.jpeg)

Afterwards, number 2 is broadcasted. The intern remains in the same location as the road with index 2 cannot be used.

Finally, number 5 is broadcasted, and the intern can traverse the corresponding road, so the intern ends up in vestige 1, which is the answer for that corresponding query.

![](_page_2_Figure_3.jpeg)

Explanation for the third sample:

For the first query the intern will traverse the first road going from vestige 1 to itself two times in a row, hence the answer for this query is 1.

The second query updates the first element of the array to 2.

During the third query the number 2 is first broadcasted to the intern located in vestige 1. Since the corresponding road is adjacent to this vestige, the intern traverses it and changes his location to vestige 2. Finally, number 1 is broadcasted, and the intern cannot traverse the corresponding road, so the intern's end location is vestige 2.

| Input      | Output |
| ----------- | ----------- |
| 5 6         |            |
| 1 2         |            |
| 3 2         |            |
| 4 2         |            |
| 2 5         |            |
| 5 1         | 1          |
| 4 5         | 1          |
| 6           | 2          |
| 2 1 4 2 5 3 |            |
| 3           |            |
| 1 3 5 2     |            |
| 1 3 5 2     |            |
| 1 1 2 3     |            |

| Input   | Output |
|---------|--------|
| 3 3     |        |
| 1 2     |        |
| 2 3     |        |
| 3 1     |        |
| 4       | 2      |
| 3 1 1 2 | 1      |
| 4       | 3      |
| 1 1 2 3 |        |
| 2 2 2   |        |
| 1 1 2 3 |        |
| 1 1 4 2 |        |

| Input   | Output |
|---------|--------|
| 2 3     |        |
| 1 1     |        |
| 1 2     |        |
| 1 2     |        |
| 4       | 1      |
| 1 1 2 3 | 2      |
| 3       |        |
| 1 1 2 1 |        |
| 2 1 2   |        |
| 1 1 2 1 |        |

## Constraints and Scoring

- 1 ≤ *N* ≤ 50
- 1 ≤ *M*, *T*, *Q* ≤ 10<sup>5</sup>
- 1 ≤ *X<sub>i</sub>*, *Y<sub>i</sub>* ≤ *N*
- 1 ≤ *A<sub>i</sub>* ≤ *M*
- 1 ≤ *L* ≤ *R* ≤ *T*
- 1 ≤ *S* ≤ *N*
- 1 ≤ *i* ≤ *T*
- 1 ≤ *K* ≤ *M*

Your solution will be tested on a set of test groups, each worth a number of points.

Each test group contains a set of test cases. To get the points for a test group, you need to solve all test cases in the test group.

| Group | Score | Limits                                                                |
|-------|-------|-----------------------------------------------------------------------|
| 1     | 7     | *Q* = 1 (The only existing query is of type 1).                      |
| 2     | 16    | *N* = 2                                                               |
| 3     | 17    | *M* = *N* - 1, *X<sub>i</sub>* = *i*, *Y<sub>i</sub>* = *i* + 1.                            |
| 4     | 31    | There are no queries of type 2. Additionally, *T* ≤ 3 ⋅ 10<sup>4</sup>. |
| 5     | 29    | No additional constraints.                                            |

Starter code:

Grader code:

Setup script:

Evaluation script: