cc是个可爱的女孩子，可爱的女孩子自然不缺人追了，某一天dd心血来潮想把追cc的N个人进行某种奇怪的排列，他给每个人分了一个id（从1开始），画在纸上，并且在其中一些点之间连了线，并且给这些线的加了权值，使得所有人组成一棵树。
然后，他想找出某个属性便于将所有人分开...在分析了所有人的各种属性之后，他发现，每个人看过的动漫数量ai是不一样的！而且恰好看过最多动漫的那个人只看过N部，而最少的看过一部。
刚上完数据结构课的cc发现dd居然在做这么无聊的一件事，于是她决定出几个问题考考dd，她随机给出三个整数l,r,p，希望dd可以告诉她所有id为ai(i∈[l,r])的点到p点的距离总和。
dd觉得这种问题简直是在侮辱他的智商，拍着胸脯立下了flag，不但能解决这个问题，甚至在中途交换某两个编号相邻的看动漫数量ai之后他依旧能很快的给出答案....
然而当cc不停的提问的时候，dd发现随着ai的交换，他的脑子越来越乱了...但是flag已经立下了，所以你可以帮他解决这个问题吗？

第一行包含两个整数N,Q表示总人数N以及询问数Q
接下去的一行包含N个整数的，表示每个人看的动漫数量a1,a2,...an,是1,2,...n的排列
接下去的N-1行每行包含三个整数x,y,z表示点x与点y相连，连线权值为z，数据保证构成一棵树
接下去的每次询问包含两行
第一行为o=1或2表示询问类型
若o=1，接下去一行包含三个整数l,r,p，如题中所述
若o=2，接下去一行包含一个整数x，表示交换ax与ax+1
输入保证1<=l,r,n<=n && l<=r, 1<=x<n
1<=n,q<=200000

对每次o=1的询问输出结果ans。

5 4
4 5 1 3 2
4 2 4
1 3 9
4 1 4
4 5 2
1
1 5 4
1
1 3 3
2
3
2
2

23
37