Value Assignment Problem 2

You will be given a Tree and an array D.

You will have to assign values in each node in the tree (say we assign and keep these values in array A and all nodes are assigned 0 initially).
To do this, you will be given the following operation to perform on the tree.

PathUpdate(u, v, p) :=
Let the nodes in the path from u to v be [a, b, c, ... d]. Assign values in these nodes taking from the D array starting from position in:
A[a] = D[p], A[b] = D[p+1], A[c] = D[p+2] ... A[d] = D[p+k-1]. (where k is the length of the path).

All updates will be consistent such that no update forces you to go out of the tree or the array.

You will also be asked to answer the following query.

Query(u) :=
Print the current value assigned to node u.

Input

The first line of input will contain two integers N and M, the number of nodes in the tree and the size of the array.

The next N-1 lines will contain two integers U and V, denoting that there is an edge between nodes U and V.

The following line will contain M integers, the values in the array D (D[1], D[2], ... D[M]).

The next line will contain an integer Q, the number of operations and queries to perform.

Next Q lines will start with 1 or 2. If it starts with 1, then three integers U, V and P will follow, denoting a Path Update operation. Otherwise, one integer U will follow, denoting a query to answer.

All the values will be in the range [1, 10^5]. All updates will be consistent such that no update forces you to go out of the tree or the array.

Output

For each query, print the desired result in a separate line.

Sample

Input	Output
8 8 1 2 1 3 2 4 2 5 2 6 4 7 4 8 1 2 3 4 5 6 7 8 9 1 7 6 4 2 2 1 5 3 4 2 2 2 1 1 1 8 5 2 1 2 2 2 4	6 5 6 5 6 7

Dataset is huge. Use faster I/O.