Description

背景：烁烁很喜欢爬树，这吓坏了树上的皮皮鼠。 题意： 给定一颗n个节点的树，边权均为1，初始树上没有皮皮鼠。 烁烁他每次会跳到一个节点u，把周围与他距离不超过d的节点各吸引出w只皮皮鼠。皮皮鼠会被烁烁吸引，所以会一直待在节点上不动。 烁烁很好奇，在当前时刻，节点u有多少个他的好朋友---皮皮鼠。 大意： 给一颗n个节点的树，边权均为1，初始点权均为0，m次操作： Q x：询问x的点权。 M x d w：将树上与节点x距离不超过d的节点的点权均加上w。

Format

Input

第一行两个正整数：n，m 接下来的n-1行，每行三个正整数u，v，代表u，v之间有一条边。 接下来的m行，每行给出上述两种操作中的一种。

Output

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

Samples

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

Limitation

数据范围：

n，m<=10^5,|w|<=10^4

注意：w不一定为正整数，因为烁烁可能把皮皮鼠吓傻了。