You are given a tree $T$ with $N$ vertices numbered $1$ to $N$. Each vertex $i$ has an integer weight $A_i$.

A connected subset $S$ of $T$ is a nonempty subset of vertices in $T$ such that, for any two vertices $a$, $b$ in $S$, there exists a path between $a$, $b$ in $T$ that only uses the vertices from $S$.

You need to perform the following $Q$ queries:

• $k$ $x$ : change $A_k$ to $x$ and print the maximum value of $\sum_{i \in S}{A_i}$ where $S$ is a connected subset of $T$.

Input

The first line contains an integer $N$ --- the number of vertices.

The second line contains $N$ integers $A_1, A_2, \dots, A_N$ separated by a space --- the weights of each vertex.

The $i$-th of the next $N - 1$ lines contains two integers $u_i$ and $v_i$ separated by a space --- the endpoints of the $i$-th edge.

The next line contains an integer $Q$ --- the number of queries.

Each of the next $Q$ lines contains two integers $k$ and $x$ separated by a space --- arguments of each query.

Output

Print $Q$ lines. In each line, print the answer to each query.

Scoring

• $1 \leq N \leq 10^5$
• $-10^9 \leq A_i \leq 10^9$ ($1 \leq i \leq N$)
• $1 \leq u_i, v_i \leq N$ ($1 \leq i \leq N-1$)
• The given graph is a tree.
• $1 \leq Q \leq 10^5$
• $1 \leq k \leq N$ for each query

• $-10^9 \leq x \leq 10^9$ for each query

• Subtask 1 (10 points): $N, Q \leq 10^3$

• Subtask 2 (20 points): Each vertex has a degree less than $3$.
• Subtask 3 (70 points): No additional constraints.

Examples

Input 1

5
3 -1 -4 -1 -5
1 2
1 3
3 4
3 5
5
1 -2
3 2
4 1
2 5
1 -9

Output 1

-1
2
3
6
5