给定一棵有 $n$ 个顶点的树，顶点编号为 $1, 2, \dots, n$。每个顶点 $i$ 被赋予一个权值 $w_i$。

你需要处理 $q$ 次操作。每种操作属于以下两种类型之一：

1. 将顶点 $v$ 的权值修改为 $x$（记作 “! $v$ $x$”）。
2. 求出与顶点 $v$ 距离小于或等于 $d$ 的所有顶点的权值之和（记作 “? $v$ $d$”）。

注意，顶点 $u$ 和 $v$ 之间的距离是它们之间最短路径上的边数。

你必须按照输入中给出的顺序回答查询（类型 2 的操作）。

输入格式

第一行包含 $n$ 和 $q$ ($1 \le n, q \le 10^5$)。第二行包含 $n$ 个整数 $w_1, w_2, \dots, w_n$ ($0 \le w_i \le 10^4$)。接下来的 $(n-1)$ 行，每行包含两个整数 $a_i$ 和 $b_i$，表示顶点 $a_i$ 和 $b_i$ 之间的一条边 ($1 \le a_i, b_i \le n$)。

接下来的 $q$ 行包含操作描述。每个操作占一行：第一个字符 $t$ 为 '!' 表示第一种操作，为 '?' 表示第二种操作。随后是 $v$ —— 顶点的编号。最后，对于类型 1 操作给出权值 $x$，对于类型 2 操作给出距离 $d$ ($1 \le v \le n, 0 \le x \le 10^4, 0 \le d \le n$)。

输出格式

对于每个查询，输出一个整数，即该查询的答案。

样例

输入 1

4 3
1 1 1 1
1 2
2 3
3 4
? 2 1
! 1 0
? 2 1

输出 1

3
2

输入 2

3 3
1 2 3
1 2
1 3
? 1 0
? 1 1
? 1 2

输出 2

1
6
6