小 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$。
| 子任务编号 | 数据范围 | 特殊性质 | 得分 |
|---|---|---|---|
| $1$ | $n,m\le 100$ | 无 | $10$ |
| $2$ | $n,m\le 2000$ | 无 | $10$ |
| $3$ | $n,m\le 100000$ | 所有点度数 $\le 2$ | $22$ |
| $4$ | $n,m\le 100000$ | 存在一个点满足度数 $=n-1$ | $15$ |
| $5$ | $n,m\le 50000$ | 无 | $15$ |
| $6$ | $n,m\le 200000$ | 无 | $28$ |
提示：UOJ 缺投。