Aliens and Planetary Paths

Aliens have visited Maribor and shared their technology and history. There are \(N+1\) planets numbered from \(0\) to \(N\), with Earth being planet \(N\). Each planet has a unique population \(P_i\). The planets are connected by \(N\) bidirectional teleporters. Teleporter \(i\) connects planets \(U_i\) and \(V_i\). The distance between two planets is defined as the minimum number of teleporters needed to travel from one to the other.

You start on Earth and plan to visit \(K\) origin planets \(A_0, A_1, \ldots, A_{K-1}\). Each origin planet is connected to Earth by exactly one teleporter. Your journey consists of taking the shortest route from Earth to each origin planet, thereby visiting all planets along these paths. Let \(S\) be the set of all planets you have visited.

The aliens will then test Earth by asking you at most \(Q\) queries of the following two types:

• Type 1: What is the size of \(S\)?
• Type 2: Given a planet \(x\), a distance \(d\), and an integer \(r\), among all planets at exactly distance \(d\) from \(x\) (where distance is measured as the number of teleporters between them), report the planet that is the \(r\)th smallest by population. That is, if you list all such planets in increasing order of \(P_i\), the answer is the planet in the \(r\)th position.

Note: There is exactly one query of Type 1.

inputFormat

The input consists of:

1. An integer \(N\) (there are \(N+1\) planets numbered \(0\) to \(N\), with Earth being \(N\)).
2. A line with \(N+1\) integers: \(P_0, P_1, \ldots, P_N\) (each representing the unique population of a planet).
3. \(N\) lines, each containing two integers \(U_i\) and \(V_i\), representing a bidirectional teleporter between planets \(U_i\) and \(V_i\).
4. An integer \(K\) representing the number of origin planets.
5. A line with \(K\) integers: \(A_0, A_1, \ldots, A_{K-1}\) (each origin planet is connected to Earth by exactly one teleporter).
6. An integer \(Q\) representing the number of queries.
7. Then \(Q\) lines follow, each describing a query. A query is formatted as follows:
   • If it is of Type 1: a single integer 1.
   • If it is of Type 2: four integers 2 x d r, where \(x\) is the starting planet, \(d\) is the distance, and \(r\) indicates the \(r\)th planet by population.

outputFormat

For each query, output the answer on a new line. For a Type 1 query, output the size of \(S\). For a Type 2 query, output the index of the planet that is the \(r\)th smallest by population among those at distance \(d\) from \(x\).

sample

3
10 20 30 40
0 1
1 2
2 3
1
2
2
1
2 1 1 1

2
0