E. Tree query with update
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a tree of n nodes. Every node has given some value. You have to process some queries and update on the tree. Queries are of two types-

$$$1$$$ $$$u$$$ $$$x$$$ $$$-$$$ Update the value of node $$$u$$$ to $$$x$$$.

$$$2$$$ $$$u$$$ $$$v$$$ $$$-$$$ Find the maximum value of all node of sub-tree v, if u is root of the tree.

Input

Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ $$$(1 \le t \le 10^4)$$$ — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer $$$n$$$ $$$(1 \le n \le 200000)$$$ — number of node in the tree.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2.., a_n$$$ $$$(1 \le a_i \le 10^9)$$$.

The $$$i$$$-th of the following $$$n−1$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$ $$$(1 \le x_i,y_i \le n, x_i ≠ y_i)$$$, meaning that the $$$i$$$ -th edge connects vertices $$$x_i$$$ and $$$y_i$$$ in the tree.

The next line of each test case contains a single integer $$$q$$$ $$$(1 \le q \le 200000)$$$.

Each of the following $$$q$$$ lines contain three integers — a description of the next action in one of the following formats:

$$$1$$$ $$$u$$$ $$$x$$$ — Update the value of node u to x $$$(1 \le u \le n, 1 \le x \le 10^9)$$$.

$$$2$$$ $$$u$$$ $$$v$$$ $$$-$$$ Find the maximum value of all node of sub-tree v, if u is root of the tree$$$(1 \le $$$u$$$,$$$v$$$ \le n)$$$.

It is guaranteed that sum of $$$n$$$ and $$$q$$$ over all test is $$$\le$$$ 200000.

Output

Print the answer for every second type of every test cases.

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