You are given a connected graph with $N$ nodes and $N$ edges. In this graph each node has a weight, and each edge has the same length of one unit. Define $D(u, v)$ as the distance between node $u$ and node $v$. Define $S(u, k)$ as the set of nodes $x$ which satisfy $D(u, x) \leq k$.

We will ask you to perform some instructions of the following forms.

• MODIFY $u$ $k$ $d$: weight of all nodes in $S(u, k)$ increase by $d$ or decrease by $-d$.
• QUERY $u$ $k$: ask for the sum of weight of all nodes in $S(u, k)$.

In the beginning, the weight of all nodes are $0$.

Input

The first line of input contains an integer $t$, the number of test cases. $t$ test cases follow.

For each test case, in the first line there is an integer $N(N \leq 100000)$.

The $i$-th line of the next $N$ line describes the $i$-th edge: two integers $u,v$ denotes an edge between $u$ and $v$.

In the next line, an integer $Q(Q \leq 100000)$ indicates the number of instructions.

Next $Q$ lines contain instructions MODIFY $u$ $k$ $d$ or QUERY $u$ $k$, where $|d| \leq 100$ and $0 \leq k \leq 2$.

Output

For each MODIFY instruction, output a integer in a line.

Example

Input

2
6
1 2
2 3
3 4
4 1
4 5
3 6
5
MODIFY 1 1 3
MODIFY 3 1 2
MODIFY 5 2 1
QUERY 3 2
QUERY 4 1
6
1 2
2 3
3 1
1 4
2 5
3 6
5
MODIFY 3 1 5
MODIFY 2 2 2
QUERY 6 1
MODIFY 4 1 -2
QUERY 2 2

Output

21
14
14
28