题目描述

给一颗 $n$ 个节点的树，边权均为 $1$，初始点权均为 $0$，$m$ 次操作：

• Q x：询问 $x$ 的点权。
• M x d w：将树上与节点 $x$ 距离不超过 $d$ 的节点的点权均加上 $w$。

输入格式

第一行两个正整数：$n,m$

接下来的 $n-1$ 行，每行三个正整数 $u,v$，代表 $u,v$ 之间有一条边。

接下来的 $m$ 行，每行给出上述两种操作中的一种。

输出格式

对于每个 Q 操作，输出当前 $x$ 节点的皮皮鼠数量。

样例输入#1

7 6
1 2
1 4
1 5
2 3
2 7
5 6
M 1 1 2
Q 5
M 2 2 3
Q 3
M 1 2 1
Q 2

样例输出

2
3
6

提示说明

对 $100\%$ 的数据：$1\leq n,m\leq10^5,|w|\leq10^4$