小 C 建立了一个存储题目的树形数据结构，想让你帮他维护。

这个数据结构是一棵树，每个节点上有一棵二叉搜索树（BST，这里指插入不旋转的平衡树）。

需要支持：

1 u v x ：小 C 出了一道难度为 $x$ 的题，选择树上 $u$ 到 $v$ 这条链上的所有节点，把 $x$ 插入到这些节点的二叉搜索树中。该操作保证 $x$ 互不相同。

插入二叉搜索树的伪代码如下：

void insert(int&p,int x){
    if(!p) return p=x,void();
    if(x<p) insert(ch[p][0],x);
    else insert(ch[p][1],x);
}

0 u w ：小 C 会在节点 $u$ 的二叉搜索树上查找一个值 $w$，如果找到 $w$ 则返回 $w$ 所在节点，否则返回下一次要走入空节点时的节点。

查找的伪代码如下：

int ask(int p,int x){
    if(x==p) return x;
    if(x<p) return ch[p][0]?ask(ch[p][0]):p;
    else return ch[p][1]?ask(ch[p][1]):p;
}

设查找到的位置为 $x$，小 C 要将节点 $u$ 的二叉搜索树上 $x$ 的祖先（包括它自己）的这些题目组成一套模拟赛。他想要计算模拟赛的难度，请你回答节点 $u$ 的二叉搜索树上 $x$ 的祖先（包括它自己）的这些题目的难度之和。

注意有可能树为空，此时请输出 $0$。

输入格式

第一行输入 $n,m$，表示树的点数、操作数。

接下来 $n-1$ 行，每行两个数 $u,v$，表示一条树边。

接下来 $m$ 行，每行为 1 u v x 或 0 u w，表示一次操作。

输出格式

输出若干行，对于每个 0 u w 操作输出一行，表示答案。

样例输入 1

3 10
1 2
2 3
1 1 2 2
1 1 3 1
1 2 3 3
0 1 1
0 1 2
0 2 1
0 2 2
0 2 6
0 3 1
0 3 4

样例输出 1

3
2
3
2
5
1
4

样例输入/输出 2~5

见下发文件。

数据范围

对于所有数据：$1\le n,m,x,w\le 2\times 10^5$。

提示：UOJ 缺投。