Harry Potter has learned a new spell: he can change the number of fruits on a tree. Overjoyed, he finds a giant fruit tree to test his new magic.

This fruit tree has $N$ nodes, where node $0$ is the root. The parent of each node $u$ is denoted as $fa[u]$, with the guarantee that $fa[u] < u$. Initially, all fruits on the tree have been cleared away by Dumbledore's magic, so every node has zero fruits.

Unfortunately, Harry's mastery of the spell is imperfect; he can only increase the number of fruits on all nodes along a path in the tree by a certain amount. Specifically, Harry's magic can be described as follows:

• Add u v d

This means adding $d$ to the number of fruits on every node along the path between nodes $u$ and $v$.

To help verify whether Harry's magic is successful, you need to provide information about the fruit tree during the process of casting spells:

• Query u

This means calculating the total number of fruits in the subtree rooted at node $u$.

Input

The first line contains a positive integer $N$ ($1 \le N \le 100\,000$), representing the total number of nodes in the fruit tree. The nodes are labeled $0, 1, \dots, N - 1$, where $0$ always represents the root.

The next $N - 1$ lines each contain two integers $a, b$ ($0 \leq a < b < N$), indicating that $a$ is the parent of $b$.

The next line contains a positive integer $Q$ ($1 \le Q \le 100\,000$), representing the total number of operations.

Following this are $Q$ lines, each being one of the following two types:

1. A u v d, which means adding $d$ to the number of fruits on all nodes along the path from $u$ to $v$; it is guaranteed that $0 \leq u, v < N$ and $0 < d < 100000$.
2. Q u, which means querying the total number of fruits in the subtree rooted at $u$, including $u$ itself; $0 \leq u < N$.

Output

For each Q operation, output the answer to the query on a new line. The answer may exceed $2^{32}$, but will not exceed $10^{15}$.

Examples

Input 1

4
0 1
1 2
2 3
4
A 1 3 1
Q 0
Q 1
Q 2

Output 1

3
3
2

Subtasks