Graph Distance Sum Query

You are given an undirected graph with n nodes, numbered from 1 to n. Each node has an initial integer value. The graph is specified by n-1 edges (forming a tree structure). You are also provided with a series of q queries. There are two types of queries:

• Query type 1 (Update Query): 1 u x. Update the value at node u to x.
• Query type 2 (Sum Query): 2 u d. Calculate and output the sum of values of all nodes that are exactly at distance d from node u (using the shortest unweighted path).

The distance between two nodes in a tree is defined as the number of edges in the shortest path connecting them. Your task is to process the queries in order and output the result for each sum query.

The answer of a query is computed using a breadth-first search starting from the given node, and summing the values of nodes which are exactly at the given distance.

Note: All queries are given on a single test case via standard input, and you should output the results to standard output.

inputFormat

The first line contains two integers n and q, representing the number of nodes and the number of queries, respectively.

The second line contains n space-separated integers, which are the initial values of the nodes.

The next n-1 lines each contain two integers u and v indicating an undirected edge between node u and node v.

The following q lines each describe a query in one of the following two formats:

• 1 u x: Update the value of node u to x.
• 2 u d: Output the sum of values of nodes that are exactly at distance d from node u.

outputFormat

For each query of type 2, output a single line containing the computed sum.

## sample

5 3
1 2 3 4 5
1 2
1 3
2 4
2 5
2 1 1
1 2 10
2 1 1

5
13

</p>