Description

小N最近在做关于树的题。今天她想了这样一道题，给定一棵N个节点的树，节点按1~N编号，一开始每个节点上的权值都是0，接下来有M个操作。第一种操作是修改，给出4个整数X,Y,A,B,对于X到Y路径上加上一个首项是A，公差是B的等差数列，因为小N十分谨慎，所以她每做完一个修改操作就会保存一次，初始状态是第0次保存的局面。第二种操作是求和，给出2个整数X,Y，输出X到Y路径上所有节点的权值和。第三种操作是读取之前第X次保存的局面，所有节点的状态回到之前第X次保存的状态。现在请你对每一个求和操作输出答案。

Format

Input

第一行2个整数N,M表示节点个数和操作次数。

接下来N-1行每行2个整数Ui,Vi表示了这棵树中Ui和Vi这2个节点间有边相连。

  接下来M行每行先有一个字符表示了操作的类型：

       如果是’c’，那么代表了一个修改操作，接下来有4个整数X1,Y1,A,B，为了使得询问在线，正确的X=X1 xor上次输出的数,Y=Y1 xor上次输出的数,如果之前没有输出过那么当成0。

       如果是’q’，那么代表了一个求和操作，接下来有2个整数X1,Y1,和修改操作一样需要xor上次输出。

       如果是’l’，那么代表了一次读取操作，接下来1个整数X1，正确的X=X1 xor上次输出的数。

Output

对于每一个求和操作，输出求和后的值。

Samples

5 7
1 2
2 3
3 4
4 5
c 2 5 2 3
c 3 4 5 10
q 1 3
l 13
q 13 15
l 6
q 6 4

12
7
7

Limitation

100%的数据中N,M<=100000,0<=A,B<=1000,0<=X1,Y1<=10^1,修改次数<M/2，不会读取没保存的局面