M. Dye Your Color
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output
There are no correct answers in life, so there is no defeat

On the mysterious continent of Ringza Ayu, there are $$$ n $$$ regions, numbered from $$$ 1 $$$ to $$$ n $$$. These $$$ n $$$ regions form a tree, meaning there are $$$ n-1 $$$ roads connecting these $$$ n $$$ regions, and for any two regions, there exists exactly one simple path that allows them to reach each other.

Initially, all $$$ n $$$ regions are uncolored. Each region can be in either a colored or uncolored state, and the pleasure value of the $$$ i $$$-th region in the uncolored state is $$$ a_i $$$. For a region, if it is currently uncolored and has a pleasure value of $$$ x $$$, then when it becomes colored, its pleasure value becomes $$$ 2 \times x $$$; if it is currently colored and has a pleasure value of $$$ x $$$, then when it becomes uncolored, its pleasure value becomes $$$\lfloor \frac{x}{2} \rfloor$$$.

Now, Boki-chan has given $$$ q $$$ operations, each of which is one of the following:

  1. Summon the Boki sprite to cast a dyeing spell on a certain region. When the Boki sprite casts a dyeing spell on the $$$ i $$$-th region, for all $$$ j $$$ that satisfy the following equation: $$$$$$ (\operatorname{lcm}(i,j))^2-(i+j) \times \operatorname{lcm}(i,j)=i \times j $$$$$$ the Boki sprite will also cast a dyeing spell on the $$$ j $$$-th region. In particular, during a single operation, the same region will only be dyed once by the Boki sprite. When a region is dyed, its dyeing state is immediately changed to colored.
  2. Change the dyeing state of a certain region to uncolored.
  3. Modify the pleasure value of a certain region. Note: This operation does not change the dyeing state of the region.

After each operation, Boki-chan wants to know the maximum pleasure value she can obtain by selecting several non-adjacent regions on the continent of Ringza Ayu.

  • Two regions $$$ u $$$ and $$$ v $$$ are adjacent if there is a road between them.
  • If the Boki sprite casts a dyeing spell on the $$$ i $$$-th region causing the $$$ j $$$-th region to also be dyed (clearly $$$ (\operatorname{lcm}(i,j))^2-(i+j) \times \operatorname{lcm}(i,j)=i \times j $$$), then for all $$$ k $$$ that satisfy $$$ (\operatorname{lcm}(j,k))^2-(j+k) \times \operatorname{lcm}(j,k)=j \times k $$$, if $$$ k \neq i $$$, the Boki sprite will also cast a dyeing spell on the $$$ k $$$-th region, and so on. Formally, this dyeing spell is transitive.
  • $$$\lfloor x \rfloor $$$ denotes the largest integer not exceeding $$$ x $$$, for example, $$$\lfloor 4 \rfloor = 4$$$, $$$\lfloor 1.2 \rfloor = 1$$$, $$$\lfloor -2.5 \rfloor = -3$$$.
Input

First, input a single integer $$$ n (1 \leq n \leq 10^5) $$$, representing the number of regions.

Next, input a line with $$$ n $$$ integers $$$ a_1, a_2, \dots, a_n (1 \leq a_i \leq 10^9) $$$, where $$$ a_i $$$ denotes the pleasure value of the $$$ i $$$-th region in the uncolored state.

Then input $$$ n-1 $$$ lines, each containing two integers $$$ u, v (1 \leq u, v \leq n) $$$, representing a road between the $$$ u $$$-th region and the $$$ v $$$-th region $$$(u,v)$$$.

Next, input a single integer $$$ q (1 \leq q \leq 5 \times 10^4) $$$, representing the number of operations.

Following this, there are $$$ q $$$ lines, each containing two or three integers, representing an operation, specifically as follows:

  • 1 x: Summon the Boki sprite to cast a dyeing spell on the $$$ x $$$-th region. Where $$$ 1 \leq x \leq n $$$.
  • 2 x: Change the dyeing state of the $$$ x $$$-th region to uncolored. Where $$$ 1 \leq x \leq n $$$.
  • 3 x y: Modify the pleasure value of the $$$ x $$$-th region to $$$ y $$$. Where $$$ 1 \leq x \leq n, 1 \leq y \leq 10^9 $$$.

It is guaranteed that the $$$ n $$$ regions form a tree.

Output

Output $$$ q $$$ lines, each containing a single integer, representing the maximum pleasure value obtained after each operation by Boki-chan.

Examples
Input
3
1 1 1
1 2
2 3
3
1 2
2 2
3 2 4
Output
3
3
4
Input
9
7 6 9 10 3 12 4 5 11
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
1
1 4
Output
73
Input
2
10 1
1 2
4
1 1
3 1 25
2 1
1 1
Output
20
25
12
24
Note

In the first sample, after the first operation, the $$$ 2 $$$-th region was dyed, and since $$$(\operatorname{lcm}(2,3))^2-(2+3) \times \operatorname{lcm}(2,3)=2 \times 3$$$, the $$$ 3 $$$-th region was also dyed. The pleasure values of the three regions are: $$$ 1, 2, 2 $$$, and Boki-chan can choose to obtain the pleasure values of the $$$ 1 $$$-th and $$$ 3 $$$-th regions, resulting in a total pleasure value of $$$ 3 $$$. It can be proven that this way maximizes the pleasure value for Boki-chan. After the second operation, according to the problem statement, the pleasure values of the three regions are: $$$ 1, 1, 2 $$$. Boki-chan can again choose to obtain the pleasure values of the $$$ 1 $$$-th and $$$ 3 $$$-th regions, resulting in a total pleasure value of $$$ 3 $$$. This way also maximizes the pleasure value for Boki-chan. After the third operation, the pleasure value of the $$$ 2 $$$-th region was modified to $$$ 4 $$$, and now the pleasure values of the three regions are: $$$ 1, 4, 2 $$$. Boki-chan can choose to obtain the pleasure value of the $$$ 2 $$$-th region, which maximizes her pleasure value.

In the second sample, after the first operation, the $$$ 4 $$$-th region was dyed, and since $$$ (\operatorname{lcm}(4,6))^2-(4+6) \times \operatorname{lcm}(4,6)=4 \times 6$$$, the $$$ 6 $$$-th region was also dyed, and because $$$ (\operatorname{lcm}(6,9))^2-(6+9) \times \operatorname{lcm}(6,9)=6 \times 9$$$, the $$$ 9 $$$-th region was also dyed. It is clear that $$$ (\operatorname{lcm}(6,4))^2-(6+4) \times \operatorname{lcm}(6,4)=6 \times 4$$$, and since the $$$ 4 $$$-th region has already been dyed, it will not be dyed again in this operation.

In the third sample, Boki-chan's optimal strategy is always to choose the pleasure value of the $$$ 1 $$$-th region. After the first operation, the pleasure value of the $$$ 1 $$$-th region becomes $$$ 20 $$$. After the second operation, the pleasure value of the $$$ 1 $$$-th region is modified to $$$ 25 $$$. After the third operation, since the state of the $$$ 1 $$$-th region changes from colored to uncolored, its pleasure value becomes $$$\lfloor \frac{25}{2} \rfloor = 12$$$. After the fourth operation, since the state of the $$$ 1 $$$-th region changes from uncolored to colored, its pleasure value becomes $$$ 12 \times 2 = 24$$$.