Troop Deployment on a Tree

In ancient times, without modern information warfare, messages were transmitted via beacon fires and rapid military maneuvers. In the country A, to minimize troop consumption, roads and deployment channels were built among n cities such that any city can reach any other and no cycles exist (i.e. they form a tree structure with city 1 as the root). Each city initially has a certain number of soldiers.

You are given a tree with n nodes (cities), rooted at city 1. The i-th city starts with an initial troop count of \(a_i\). Then, m commands are issued to adjust the troop counts, followed by q queries.

There are two types of commands:

• 1 x y: Increase the troop count by \(y\) for city x and all cities in its subtree (i.e. all descendants of x in the tree).
• 2 x y: Increase the troop count by \(y\) for city x and all cities directly connected to it (i.e. its parent and its children in the tree).

After executing all m commands, q queries are asked. Each query provides an integer x and you must output the final troop count in city x.

Input/Output Format details are provided below.

inputFormat

The input is given as follows:

1. The first line contains three integers: n (1 ≤ n), m (number of commands), and q (number of queries).
2. The second line contains n integers: \(a_1, a_2, \ldots, a_n\) representing the initial troop count in each city.
3. The next n - 1 lines each contain two integers u and v, indicating that there is an edge between city u and city v (forming a tree with city 1 as the root).
4. The following m lines each contain a command in one of the following forms:
   • 1 x y — add y troops to city x and all cities in its subtree.
   • 2 x y — add y troops to city x and all directly connected cities (its parent and children).
5. The last q lines each contain a single integer x, representing a query for the final troop count in city x.

outputFormat

For each query, output the final troop count of the queried city on a separate line.

sample

5 3 3
10 20 30 40 50
1 2
1 3
2 4
2 5
1 2 5
2 3 10
1 1 3
1
2
4

23
28
48