Process Tree Operations

You are given a tree with n nodes numbered from 1 to n. The tree is defined by n-1 edges. You need to perform a series of operations on the tree. There are two types of operations:

• Update Operation: 1 u x — Add an integer x to every node in the subtree of node u.
• Query Operation: 2 v — Query the current value at node v.

To support these operations efficiently, you can use an Euler tour of the tree and a Binary Indexed Tree (BIT). Formally, if we denote by start[u] and end[u] the discovery and finishing times of node u in the DFS traversal, then an update on the subtree of u can be performed by executing:

$$\text{update}(start[u], x) \quad \text{and} \quad \text{update}(end[u]+1, -x) $$

For each query on node v, the answer is the prefix sum at start[v] in the BIT.

inputFormat

The first line contains an integer n representing the number of nodes in the tree.

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

The following line contains an integer m representing the number of operations.

Each of the next m lines describes an operation in one of the following two formats:

• Update: 1 u x
• Query: 2 v

All input values are given via standard input.

outputFormat

For each query operation (of the form 2 v), output the resulting integer on a new line. The outputs should be printed to standard output.

## sample

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

10
5

</p>