小 Z 有一棵 $n$ 个节点构成的树,这棵树以点 $1$ 为根,边权均为 $1$ ,每个节点 $x$ 有点权 $a_x$ ,初始所有节点的权值为 $0$ .

小 Z 想对这棵树进行总共 $m$ 次操作,并且 小 Z 希望能够支持以下四种类型的操作:

1. 给定 $x,y,k,v$ ,对满足节点 $i$ 到树上唯一的最短路径 $(x,y)$ 的最短距离 $\leq k$ 的所有节点 $i$ 的权值增加 $v$ ,即 $a_i \leftarrow a_i+v$ .
2. 给定 $x,v$ ,将点 $x$ 的子树内的所有节点 $i$ 的权值增加 $v$ ,即 $a_i \leftarrow a_i+v$ .
3. 给定 $x,y,k$ ,查询所有满足节点 $i$ 到树上唯一的最短路径 $(x,y)$ 的最短距离 $\leq k$ 的所有节点 $i$ 的权值的和.
4. 给定 $x$ ,查询点 $x$ 的子树内的所有节点 $i$ 的权值和.

由于答案会比较大,输出对 $2^{64}$ 取模即可.

输入格式

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

接下来第 $2$ 行到第 $n$ 行每行两个正整数 $u,v$ 来描述树上的一条边.

接下来 $m$ 行,每行先给出一个操作类型 $op$ .

当 $op=1$ 时给定 $x,y,k,v$ 来描述操作一;

当 $op=2$ 时给定 $x,v$ 来描述操作二;

当 $op=3$ 时给定 $x,y,k$ 来描述操作三;

当 $op=4$ 时给定 $x$ 来描述操作四.

输出格式

对于每个操作 $3$ 和操作 $4$ ,输出其对应的答案对 $2^{64}$ 取模的结果.

数据范围

数据范围: $1 \leq n,m \leq 2 \times 10^5 , 1 \leq x,y \leq n , 1 \leq v \leq 10^9 ,0 \leq k \leq 3$ .

时间限制 7s ,空间限制 1G .

部分分

数据范围: $1 \leq n,m \leq 2 \times 10^5 , 1 \leq x,y \leq n , 1 \leq v \leq 10^9 ,0 \leq k \leq 3$ .

子任务 1 (10分) : $1 \leq n , m \leq 5 \times 10^3$ .

子任务 2 (10分) : $k=0$ .

子任务 3 (5分) : 保证树形态构成一条形如 $1$ 连接 $2$ 连接 $...$ 连接 $n$ 的链(所有边均可以表示为 $i$ 连接 $i+1$ 的形式).

子任务 4 (10分) : 保证 $k=1$ ,操作类型只包含操作一和操作三,并且操作一和操作三满足 $x=y$ ,即修改和查询的链是单点.

子任务 5 (10分) : 保证操作类型只包含操作一和操作三,并且操作一和操作三满足 $x=y$ ,即修改和查询的链是单点.

子任务 6 (15分) : 保证操作一和操作三满足 $x=y$ ,即修改和查询的链是单点.

子任务 7 (15分) : $k \leq 1$ .

子任务 8 (25分) : 无特殊限制.