ami có một cái cây gốc là 1, mỗi nút có 1 giá trị \(a_i\). Cần thực hiện các truy vấn sau:

1. 1 u val : gán nút \(u\) giá trị bằng \(val\).

2. 2 u : Tính tổng giá trị trên các nút là cháu của \(u\) (bao gồm \(u\)).

Input

Dòng đầu tiên chứa \(t\) là số câu hỏi.

Mỗi câu hỏi có dạng sau:

• Dòng đầu tiên chứa 1 số nguyên \(N\) là số đỉnh của cây.
• Dòng tiếp theo chứa \(n\) số nguyên \(a_i\) là giá trị nút \(i\).
• \(N-1\) dòng tiếp theo, mỗi dòng chứa 2 số \(u\) và \(v\) là một cạnh của cây.
• Tiếp theo là số nguyên \(q\) là số truy vấn.
• \(q\) dòng tiếp theo, mỗi dòng chứa một loại câu hỏi đã nêu trên.

Output

Đáp án của mỗi truy vấn loại 2.

Example

1
3
1 2 3
1 2
2 3
3
2 1
1 3 4
2 1

6
7

Giới hạn

• \(\sum n, q \leq 5 \cdot 10^6\)
• \(1 \leq a_i \leq 10^9\)
• \(1 \leq n \leq 10^5\)
• \(1 \leq u, v \leq N, u \neq v\)