Weighted Tree Queries

You are given a tree with n nodes where each node has an initial weight. The tree is rooted at node 1. You need to process q queries. There are two types of queries:

• Update Query: 1 x y — update the weight of node x to y.
• Find Query: 2 x — output the sum of the weights in the subtree of node x (including x itself).

Note: For every update query, you must update the subtree sum for every ancestor of the updated node accordingly. The DFS order is used to compute parent-child relationships.

The input is read from stdin and the output is written to stdout.

inputFormat

The first line contains a single integer n — the number of nodes in the tree.

The second line contains n space-separated integers, the initial weights of the nodes (nodes are numbered from 1 to n).

Each of the next n-1 lines contains two integers u and v denoting an undirected edge between nodes u and v.

The next line contains a single integer q — the number of queries.

Each of the following q lines describes a query in one of the following formats:

• 1 x y: Update the weight of node x to y.
• 2 x: Print the sum of the weights in the subtree of node x.

outputFormat

For each query of type 2, output the corresponding subtree weight sum on a new line.

## sample

5
2 1 4 2 6
1 2
1 3
3 4
3 5
3
2 1
1 3 5
2 3

15
13

</p>