给定一个含有 $N$ 个节点和 $N$ 条边的连通图。在这个图中，每个节点都有一个权值，每条边的长度均为 $1$ 个单位。定义 $D(u, v)$ 为节点 $u$ 和节点 $v$ 之间的距离。定义 $S(u, k)$ 为满足 $D(u, x) \leq k$ 的节点 $x$ 的集合。

你需要执行以下格式的一些操作。

• MODIFY $u$ $k$ $d$：将 $S(u, k)$ 中所有节点的权值增加 $d$。
• QUERY $u$ $k$：查询 $S(u, k)$ 中所有节点的权值之和。

初始时，所有节点的权值均为 $0$。

输入格式

第一行输入包含一个整数 $t$，表示测试数据的组数。接下来是 $t$ 组测试数据。

对于每组测试数据，第一行包含一个整数 $N$ ($N \leq 100000$)。

接下来的 $N$ 行中，第 $i$ 行描述第 $i$ 条边：两个整数 $u, v$ 表示 $u$ 和 $v$ 之间有一条边。

接下来的一行包含一个整数 $Q$ ($Q \leq 100000$)，表示操作的数量。

接下来的 $Q$ 行，每行包含一个操作 MODIFY $u$ $k$ $d$ 或 QUERY $u$ $k$，其中 $|d| \leq 100$ 且 $0 \leq k \leq 2$。

输出格式

对于每个 MODIFY 操作，在一行中输出一个整数。

样例

输入样例 1

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

输出样例 1

21
14
14
28