给你一棵含有 $N$ 个结点的树 $T$，结点编号为 $1$ 到 $N$。每个结点 $i$ 都有一个整数权值 $A_i$。

树 $T$ 的一个连通子集 $S$ 是指 $T$ 的一个非空结点子集，满足对于 $S$ 中的任意两个结点 $a$ 和 $b$，$T$ 中连接 $a$ 和 $b$ 的路径上所有的结点都属于 $S$。

你需要执行以下 $Q$ 次查询：

• $k$ $x$：将 $A_k$ 修改为 $x$，并输出 $\sum_{i \in S}{A_i}$ 的最大值，其中 $S$ 是 $T$ 的一个连通子集。

输入格式

第一行包含一个整数 $N$，表示结点数量。

第二行包含 $N$ 个由空格隔开的整数 $A_1, A_2, \dots, A_N$，表示每个结点的权值。

接下来的 $N - 1$ 行中，第 $i$ 行包含两个由空格隔开的整数 $u_i$ 和 $v_i$，表示第 $i$ 条边的两个端点。

下一行包含一个整数 $Q$，表示查询的数量。

接下来的 $Q$ 行中，每行包含两个由空格隔开的整数 $k$ 和 $x$，表示每次查询的参数。

输出格式

输出 $Q$ 行。每行输出对应查询的答案。

数据范围

• $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$)
• 给定的图是一棵树。
• $1 \leq Q \leq 10^5$
• 对于每次查询，$1 \leq k \leq N$
• 对于每次查询，$-10^9 \leq x \leq 10^9$

子任务

• 子任务 1（10 分）：$N, Q \leq 10^3$
• 子任务 2（20 分）：每个结点的度数均小于 $3$。
• 子任务 3（70 分）：无附加限制。

样例

输入样例 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

输出样例 1

-1
2
3
6
5