Simplest queries on a tree

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\(\ v \ x\) — add \(x\) to the value of \(a\) for all vertices in the subtree of vertex \(v\).

• 2\(\ v\) — find the maximum value 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\), which are stored in the vertices.

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

Next is the 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 2 37 2 2 2 1 1 3 43 2 1	7 7 44 44 47

Notes

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

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

• The subtree of vertex \(1\) is the entire tree. The answer is \(\max a = 7\).

• The subtree of vertex \(2\) consists of vertices \(2\), \(4\), \(5\). After increasing \(a_2\), \(a_4\), and \(a_5\) by \(37\), the array \(a\) becomes \((4, 44, 4, 44, 41)\).

• The subtree of vertex \(2\) consists of vertices \(2\), \(4\), \(5\). The answer is \(\max \{a_2, a_4, a_5\} = \max \{44, 44, 41\} = 44\).

• The subtree of vertex \(1\) is the entire tree. The answer is \(\max a = 44\).

• The subtree of vertex \(3\) contains a single vertex \(3\). After increasing \(a_3\) by \(43\), the array \(a\) becomes \((4, 44, 47, 44, 41)\).

• The subtree of vertex \(1\) is the entire tree. The answer is \(\max a = 47\).