Description

有一棵树，其节点用$1, 2, …, n$ 标 记。开始时，第$i$个节点的权值为$w_i$ 。有$q$ 个操作，操作分为两种类 型：①$!$ $v$ $x$ ，将节点$v$ 的权值修改为$x$ ；②$?$ $v$ $d$ ，查询到$v$ 距离不 超过$d$ 的所有节点的权值之和。节点$u$ 和$v$ 之间的距离是它们之间最短 路径上的边数。

Format

Input

包括几个测试用例。每个测试用例的第$1$行都包含$n 、q$ $（1≤n ，q ≤10^5 ）$；第$2$行都包含$n$ 个整数$w_ 1 , w_2 , …, w_n （0≤w_n≤10^4 ）$；接下来的$n -1$行，每行都包含两个整数$a_i$ 、$b_i$ ，表示在$a_i$ 和$b_i$ 节点之间有一条边$（1≤a_i ，b_i ≤n ）$。接下来是$q$行操作 $（1≤v ≤n ，0≤x ≤10^4 ，0≤d ≤n ）$。

Output

对每个查询，都单行输出权值之和。

Samples

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

3
2
1
6
6