Bảo is a diligent lumberjack and he is in charge of managing a large, enchanted grove. This grove is quite special: it contains ~n~ ancient trees, each tree ~i~ has an enchantment level of ~a_i~.

The entire grove is interconnected by ~n - 1~ logging paths such that one can travel from any tree to any other tree. The ~j~-th path connects tree ~u~ to tree ~v~ (~u \neq v~). Initially, the entire grove is considered one single, connected "logging zone". The value of a logging zone is the total enchantment level of all trees in that zone.

Every day of Bảo's work, there will be ~q~ events that happened. The events are of three types:

• ~1~ ~x~ — The Cut. Bảo is instructed to permanently remove the ~x~-th logging path. This action will split a single logging zone into two smaller ones. After cutting, Bảo must report the absolute difference between the value of first new zone and the value of second new zone.

• ~2~ ~u~ ~y~ — The Growth. The enchantment level of tree ~u~ suddenly changes by ~y~ (its new value becomes ~a_u = a_u + y~).

• ~3~ — The Boss's Report. Bảo must immediately report to his Boss the value of the most valuable logging zone.

Bảo is sick, can you help him manage the grove for today.

Input

The first line contains a positive integer ~T~ (~T \le 1000~) — the number of test cases.

The first line of each test case contains a positive integer ~n~ (~1 \le n \le 2 \cdot 10^5~) — the number of trees in the grove.

The second line of each test case contains ~n~ integers ~a_1, a_2, \ldots, a_n~ (~|a_i| \le 10^9~) — the enchantment level of each trees.

The next ~n - 1~ lines of each test case contain two integers ~u~ and ~v~ (~1 \le u, v \le n~) — indicating that there is a logging path connecting tree ~u~ and tree ~v~.

The ~n + 2~-th line of each test case contains a positive integer ~q~ (~1 \le q \le 2 \cdot 10^5~) — the number of events.

The next ~q~ lines of each test case are one of the following three types:

• ~1~ ~x~ (~1 \le x \le n - 1~)

• ~2~ ~u~ ~y~ (~1 \le u \le n~, ~|y| \le 10^9~)

• ~3~

For each test case, the total number of type ~1~ queries is guaranteed to appear exactly ~n - 1~ times with distinct values of ~x~.

The total ~n~ is guaranteed not to exceed ~2 \cdot 10^5~ across all tests. The total ~q~ is guaranteed not to exceed ~2 \cdot 10^5~ across all tests.

Output

For each type ~1~ and ~3~ query, output the answer on a new line.

Sample Input 1

1
6
1 1 1 1 1 1
2 6
2 1
4 2
3 4
2 5
5
3
2 2 -6
3
1 2
3

Sample Output 1

6
0
2
1

Notes

In the first example, the following events happened:

• In the first event there is only one logging zone. So the most valuable logging zone has value ~1 + 1 + 1 + 1 + 1 + 1 = 6~.

  

  The initial grove

• In the second event, the second tree's enchantment value got reduced by ~6~.

• In the third event, the most valuable logging zone's value is ~1 + (-5) + 1 + 1 + 1 + 1 + 1 = 0~.

• In the fourth event, the second logging path is removed. There will be ~2~ logging zones. The green colored logging zone (in the second figure) has value ~(-5) + 1 + 1 + 1 + 1 = -1~. The blue colored logging zone has value ~1~. Therefore, the absolute different between two logging zones are ~|1 - (-1)| = 2~.

  

  The grove after the fourth event

• In the fifth event, there are logging zones with values ~1~ and ~-1~. Therefore ~1~ will be report to Bảo's boss.