Ancient Buildings Sequence Navigation

In Moldova, alongside the Rute River, there is a famous ancient building complex. The complex consists of \(N\) ancient buildings and \(M\) directed roads. The roads are numbered in order of input from \(1\) to \(M\).

Scientists recently discovered a mysterious sequence left behind by the Cucuteni culture! This sequence contains \(T\) integers, each between \(1\) and \(M\). To uncover the secret of the sequence, an intern is asked to perform the following task:

The intern starts at some building. Then the scientists recite a subsequence of the mysterious sequence. Suppose the intern is currently at building \(X\) and the recited number is \(Z\). Then:

• If the starting point of road \(Z\) is exactly \(X\), the intern follows that road to the connected building.
• Otherwise, the intern stays at his current building.

During the 8th EJOI, the local scientists have \(Q\) queries for you:

• 1 L R S: If the intern initially starts at building \(S\) and the scientists recite the \(L\)th to the \(R\)th terms of the mysterious sequence, determine at which building the intern stops.
• 2 i K: Update the \(i\)th term of the mysterious sequence to \(K\).

For each query of type 1, output the resulting building number.

inputFormat

The first line contains three integers \(N\), \(M\) and \(T\) ( \(1 \leq N, M, T\) ).
The next \(M\) lines each contain two integers \(u\) and \(v\) representing a directed road from building \(u\) to building \(v\). Roads are numbered in the order of input from \(1\) to \(M\).
The following line contains \(T\) integers, the mysterious sequence. Each is between \(1\) and \(M\).
The next line contains an integer \(Q\), the number of queries.
Each of the next \(Q\) lines describes a query in one of the following formats:

• 1 L R S
• 2 i K

outputFormat

For each query of type 1, print the final building number on a new line.

sample

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

3
3
3