# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

## Value Assignment Problem 2

Limits: 2s, 512 MB

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.

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.

### Samples

InputOutput
```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.

Author

Discussion