在 ICPCCamp 中，有 $n$ 座城市，编号为 $1, 2, \dots, n$，由 $(n - 1)$ 条双向道路连接。保证任意两座不同城市之间有且仅有一条路径。

在每座城市 $i$ 中，都有一座防御塔，其能量为 $a_i$，建造顺序为 $n, (n - 1), \dots, 1$。防御塔的编号与城市编号相同。因此，塔 $n$ 是最古老的塔，而塔 $1$ 是最新的塔。塔 $i$ 对城市 $j$ 的影响定义为 $eff(i, j) = a_i - \delta(i, j)$，其中 $\delta(i, j)$ 是城市 $i$ 和城市 $j$ 之间的道路条数。城市 $j$ 的守护者是所有对该城市影响最大的塔。如果有多座塔对同一城市的影响相同，则选择其中最古老的一座作为该城市的守护者。

Yuuka 发出了 $q$ 条指令来升级防御塔的能量，其中第 $k$ 条指令是为塔 $w_k$ 增加 $d_k$ 点能量。在每条指令执行后，她想知道所有城市守护者的编号之和。注意，被升级的塔会自动成为最新的塔。

然而，这里有一个限制：升级塔是一项昂贵的操作。如果被升级的塔甚至不是其所在城市的守护者，或者 $d_k = 0$，则该升级指令会被忽略。

输入格式

输入包含零个或多个测试用例，并以文件结束符（EOF）终止。对于每个测试用例：

第一行包含两个整数 $n$ 和 $q$ ($1 \le n, q \le 10^5$)。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($0 \le a_i \le 10^9$)。

接下来的 $(n - 1)$ 行中，第 $i$ 行包含两个整数 $u_i$ 和 $v_i$，表示城市 $u_i$ 和 $v_i$ 之间的一条道路 ($1 \le u_i, v_i \le n$)。保证任意两座不同城市之间有且仅有一条路径。

最后 $q$ 行中，第 $k$ 行包含两个整数 $w_k$ 和 $d_k$ ($1 \le w_k \le n, 0 \le d_k \le 10^9$)。

保证所有测试用例的 $n$ 之和与 $q$ 之和均不超过 $10^5$。

输出格式

对于每个测试用例，输出 $q$ 个整数 $s_1, s_2, \dots, s_q$，其中 $s_k$ 表示第 $k$ 条指令执行后所有城市守护者的编号之和。

样例

样例输入 1

3 3
1 1 0
1 3
2 3
1 2
2 2
3 1000000000
4 2
2 4 4 4
4 1
4 2
3 1
2 4
2 3

样例输出 1

4
4
4
8
8