Description

给出一个\(n\)个节点的树，其中\(1\)号节点为根，所有边长度为\(1\)，初始所有节点权值为\(0\)。
请支持如下两种操作：
\(1\) \(d\) \(x\)，表示将所有深度为\(d\)的节点权值加上\(x\)，深度定义为其到\(1\)号点最短路的长度。
\(2\) \(a\)，表示查询以\(a\)为根的子树的点权和。
数据结构选手，给我上。

Format

Input

每个测试点仅包含一组输入数据。
第一行两个整数\(n,m(1<=n,m<=10^5)\)，表示树的节点数和操作总数。
接下来\(n-1\)行，每行两个整数\(u,v(1<=u,v<=n)\)，表示在节点\(u\)和节点\(v\)之间有一条边。
接下来\(m\)行，每行是如下两种形式之一：
\(1\) \(d\) \(x(0<=d<n,|x|<=10^8)\)，表示进行第一类操作。
\(2\) \(a(1<=a<=n)\)，表示进行第二类操作，你需要输出答案。
保证输入数据为一棵树。

Output

按照输入顺序，对于每个询问，输出一行一个整数表示答案。

Sample 1

Input

5 5
1 2
2 3
2 4
1 5
1 1 2
1 2 -1
2 1
1 2 3
2 2

Output

2
6

Limitation

1s, 1GB for each test case.

Source

Vijos Original