bobo has a tree, whose vertices are conveniently labeled by 1,2,…,n. At the very begining, the i-th vertex is assigned with weight w _i.

There are q operations. Each operations are of the following 2 types:

Change the weight of vertex v into x (denoted as "! v x"),
Ask the total weight of vertices whose distance are no more than d away from vertex v (denoted as "? v d").

Note that the distance between vertex u and v is the number of edges on the shortest path between them.

The input consists of several tests. For each tests:

The first line contains n,q (1≤n,q≤10 ⁵). The second line contains n integers w ₁,w ₂,…,w _n (0≤w _i≤10 ⁴). Each of the following (n - 1) lines contain 2 integers a _i,b _i denoting an edge between vertices a _i and b _i (1≤a _i,b _i≤n). Each of the following q lines contain the operations (1≤v≤n,0≤x≤10 ⁴,0≤d≤n).

For each tests:

For each queries, a single number denotes the total weight.