题目描述
Pussycat Sonya has a tree (a connected graph without cycles) with N nodes, numbered 1 through N.
Each node has some weight Wi. Sonya has asked Q queries of two types.
The first type is of form "1 U X".
You should change the weight of the node U to X.
The second type is of form "2 K U V".
Find the K-th smallest weight in a subtree of U for the tree rooted in V.
More formally:
1) Root the tree in the node V.
2) Consider the list of weights of all vertices in a subtree of the node U.
3) Sort the list non-decreasingly.
4) Print in one line the K-th element of the list.
It's guaranteed that for each query of the second type the number K won't exceed the size of the subtree.
Thus, the described list contains at least K weights so the answer exists.
Input format
The first N+1 lines describe a tree.
The first of them contains a single integer N, the number of nodes in a tree.
The next N-1 lines contain 2 integers each, denoting two vertices connected by an edge.
The next line contains N space-separated integers, W1, W2, ..., WN.
Then, the queries are given.
One line contains a single integer Q, the number of queries.
Finally, each of the last Q lines contains one query of form "1 U X" or "2 K U V", where all numbers are integers.
Output format
For each query of the second type print the answer in a separate line.
Constraints
1 ≤ N, Q ≤ 10^5
1 ≤ Wi, X ≤ 10^6
1 ≤ K, U, V ≤ N
SAMPLE INPUT
12
1 2
1 8
2 3
2 6
2 7
3 4
3 5
8 9
8 10
10 11
10 12
1 2 3 4 5 6 7 8 9 10 11 12
5
2 5 2 1
1 6 100
2 5 2 1
2 9 8 10
2 4 8 3
SAMPLE OUTPUT
6
7
100
11
Explanation
The given tree consists of 12 nodes. You have to handle 5 queries and the first 3 of them are explained below:
Query #1
Tree is rooted in the node 1.
We consider all nodes in a subtree of the node 2.
The indices of nodes in a subtree are: 2, 3, 6, 7, 4, 5.
Let's sort their weights in non-decreasing order: 2, 3, 4, 5, 6, 7.
The 5-th smallest weight is 6.
Query #2
Weight of the node 6 changes to 100.
Query #3
Tree is rooted in the node 1, so we have the same nodes in the subtree of node 2: 2, 3, 6, 7, 4, 5. But their weights in non-decreasing order are now: 2, 3, 4, 5, 7, 100. Thus, the 5-th smallest weight is 7.
输入格式
见题面
输出格式
见题面