More Complex Tree Queries

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

Given a rooted tree with \(n\) vertices, numbered from \(1\) to \(n\). The root of the tree is vertex \(1\). Each vertex \(v\) contains an integer \(a_v\).

You need to process \(q\) queries of two types.

• 1\(\ u \ v \ x\) — increment the value of \(a\) for all vertices on the path from \(u\) to \(v\) by \(x\).

• 2\(\ v\) — find the sum of values of \(a\) in the subtree of vertex \(v\).

Input

The first line contains an integer \(n\) — the number of vertices in the tree.

The second line contains \(n\) integers \(a_v\), written in the vertices.

The next \(n - 1\) lines contain two integers \(u\), \(v\) — the numbers of vertices connected by an edge.

Next is an integer \(q\) — the number of queries.

The next \(q\) lines contain queries in the format described above.

Output

For each query of the second type, output the answer on a separate line.

Constraints

\(1 \le n \le 2 \cdot 10^5\),

\(1 \le q \le 2 \cdot 10^5\),

\(1 \le a_v, x \le 10^9\).

Samples

Input (stdin) сopy	Output (stdout) сopy
5 4 7 4 7 4 1 2 1 3 2 4 2 5 7 2 2 2 1 1 4 5 2 2 2 2 1 1 4 3 7 2 1	18 26 24 32 60

Notes

Initially \(a = (4, 7, 4, 7, 4)\).

• The subtree of vertex \(2\) consists of vertices \(2\), \(4\), \(5\). The answer is \(a_2+a_4+a_5=7+7+4=18\).

• The subtree of vertex \(1\) is the entire tree. The answer is \(a_1+a_2+a_3+a_4+a_5=4+7+4+7+4=26\).

• On the path from vertex \(4\) to vertex \(5\) lie vertices \(4\), \(2\), \(5\). After increasing \(a_4\), \(a_2\), \(a_5\) by \(2\), the array \(a\) becomes \((4, 9, 4, 9, 6)\).

• The subtree of vertex \(2\) consists of vertices \(2\), \(4\), \(5\). The answer is \(a_2+a_4+a_5=9+9+6=24\).

• The subtree of vertex \(1\) is the entire tree. The answer is \(a_1+a_2+a_3+a_4+a_5=4+9+4+9+6=32\).

• On the path from vertex \(4\) to vertex \(3\) lie vertices \(4\), \(2\), \(1\), \(3\). After increasing \(a_4\), \(a_2\), \(a_1\), \(a_3\) by \(7\), the array \(a\) becomes \((11, 16, 11, 16, 6)\).

• The subtree of vertex \(1\) is the entire tree. The answer is \(a_1+a_2+a_3+a_4+a_5=11+16+11+16+6=60\).