魔法树

给定一棵包含 $n$ 个节点的树，节点编号为 $0$ 到 $n-1$，根节点为 $0$。初始时，每个节点的权值均为 $0$。

你需要依次处理以下两类操作：

• Add $x$ $y$ $d$：将节点 $x$ 到节点 $y$ 的唯一简单路径上的每个节点（包括 $x$ 和 $y$）的权值增加 $d$。
• Query $x$：询问以节点 $x$ 为根的子树中所有节点的权值之和。树中的父子关系由以节点 $0$ 为根的整棵树确定，且子树包含节点 $x$ 本身。

输入格式

第一行包含一个整数 $n$，表示树的节点数。

接下来 $n-1$ 行，每行包含两个整数 $u$ 和 $v$，表示节点 $u$ 与节点 $v$ 之间有一条无向边。输入的边保证构成一棵树。

下一行包含一个整数 $m$，表示操作数。

接下来 $m$ 行，每行包含一条操作，格式为 Add $x$ $y$ $d$ 或 Query $x$。

输出格式

对于每条 Query 操作，输出一行一个整数，表示所询问子树中所有节点的当前权值之和。

样例输入

4
0 1
1 2
2 3
4
Add 1 3 1
Query 0
Query 1
Query 2

样例输出

3
3
2

数据范围

• $1\le n,m\le 10^5$；
• $0\le u,v,x,y<n$，且输入的边构成一棵树；
• $1\le d\le 10^4$；
• 所有节点权值之和及查询结果均使用 $64$ 位有符号整数表示。

来源与许可

本题题面与测试数据整理自 BZOJ。

样例 1

输入

4
0 1
1 2
2 3
4
Add 1 3 1
Query 0
Query 1
Query 2

输出

3
3
2