Description

The game is played on a tree of size $n$. Each node has a weight, and the weight of node $i$ is $w_i$.

Each time, the system provides a path. Xiao A can pick two nodes $x, y$ on this path with different weights. His score is $w_x \bmod w_y$. Then Xiao B will pick two nodes from the entire tree that Xiao A has not picked before, and the scoring method is the same as Xiao A's.

To keep the game challenging, the system sometimes increases the weight of a node.

Of course, Xiao A will try his best to maximize his score, and he wants to know what this maximum value is. At the same time, he also wants to know, when his own score is maximized, what Xiao B's maximum score is.

Input Format

The first line contains an integer $n$, the number of nodes in the tree.

The next $n-1$ lines each contain two integers $a, b$, indicating that there is an edge between $a$ and $b$.

The next line contains $n$ integers, where the $i$-th number is the weight of node $i$.

The next line contains an integer $q$.

The next $q$ lines each contain three integers $opt, x, y$.

If $opt=0$, increase $w_x$ by $y$.

If $opt=1$, it means the system provides a path from $x$ to $y$.

Output Format

For each query with $opt=1$, output one line with two integers $suma, sumb$, representing Xiao A's maximum score, and Xiao B's maximum score under this condition.

If Xiao A cannot pick two nodes with different weights, output only one number $-1$.

7
1 2
2 3
2 4
1 5
5 6
5 7
5 4 3 2 1 4 3
6
1 3 4
1 2 5
1 2 1
0 2 1
1 2 5
1 2 1

3 4
4 3
4 3
1 4
-1

Hint

Explanation of the samples:

First time: Xiao A chooses nodes $3$ and $2$, scoring $3 \bmod 4 = 3$. Xiao B chooses nodes $6$ and $1$, scoring $4 \bmod 5 = 4$.

Second time: Xiao A chooses nodes $2$ and $1$, scoring $4 \bmod 5 = 4$. Xiao B chooses nodes $7$ and $6$, scoring $3 \bmod 4 = 3$.

Third time: Xiao A chooses nodes $2$ and $1$, scoring $4 \bmod 5 = 4$. Xiao B chooses nodes $7$ and $6$, scoring $3 \bmod 4 = 3$.

Fourth time: the weight of node $2$ becomes $5$.

Fifth time: Xiao A chooses nodes $5$ and $1$, scoring $1 \bmod 5 = 1$. Xiao B chooses nodes $6$ and $2$, scoring $4 \bmod 5 = 4$.

Sixth time: the only nodes Xiao A can choose are $1, 2$, and both have weight $5$, so there is no valid choice.

This problem uses bundled testdata.

Constraints: for all data, $1 \leq n,q \leq 10^5$, $1 \leq w_i \leq 10^4$, the added value is a positive integer not greater than $10^3$, and the input is a valid tree. It is guaranteed that at any time, the number of distinct values is at least $4$.

Translated by ChatGPT 5