# Query on a graph

Time Limit: 6000/3000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

## Description

You are given a connected simple graph(in which both multiple edges and loops are disallowed) 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) ≤ 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 ≤ 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 ≤ 100000) indicates the number of instructions. Next Q lines contain instructions MODIFY u k d or QUERY u k, where |d|≤ 100 and 0 ≤ k ≤ 2.

## Output

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

## Sample 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

## Sample Output

21
14
14
28

jiangzijing2015

## Source

2016ACM/ICPC亚洲区沈阳站-重现赛（感谢东北大学）