题目描述

从前有一棵以1为根的有根树，树的每个节点有一个权值。

现在请你维护如下操作：

• 1、令节点 x 的权值增加y
• 2、询问以节点 x 为根的子树中所有节点的权值和。

输入格式

第一行两个整数n，m，分别表示树的节点数及操作数。

接下来n-1行每行两个整数x、y，表示树中的一条边。

接下来m行每行一个操作，其中“1 x y z”表示将节点x到节点y的路径中的每一个节点y增加z，“2 x”表示询问以节点 x 为根的子树中所有节点的权值和。

输出格式

对于每个“2 x”的询问，输出其结果。

样例数据

输入1

4 4
1 2
1 3
2 4
1 2 3 3
1 4 2 1
2 4
2 1

输出1

1
11

数据规模与约定

对于100%的数据n<=100000, m<=200000, x、y<=n, |z|<=1000000