T635263 [Codechef FEB13] Obserbing the tree树上询问

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

第一行两个整数 n,mn,m 表示节点个数和操作次数。 接下来 n-1n−1 行每行 22 个整数 u_i,v_iu i ​ ,v i ​ 表示了这棵树中 u_iu i ​ 和 v_iv i ​ 这 22 个节点间有边相连。 接下来 mm 行每行先有一个字符表示了操作的类型；同时为了保证在线，我们设 tt 表示上一次输出的答案： 如果是 c，那么代表了一个修改操作，接下来有 44 个整数 x1,y1,a,bx1,y1,a,b，为了使得询问在线，正确的 x=x1\text{ xor }tx=x1 xor t，y=y1\text{ xor }ty=y1 xor t，如果之前没有输出过那么当成 00。 如果是 q，那么代表了一个求和操作，接下来有两个整数 x1,y1x1,y1，和修改操作一样需要 \text{xor }txor t。 如果是 l，那么代表了一次读取操作，接下来一个整数 x1x1，正确的 x=x1\text{ xor }tx=x1 xor t。

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

100% 的数据中 n,m \leq 10^5n,m≤10 5 ，0 \leq a,b \leq 10000≤a,b≤1000，0 \leq x1,y1 \leq 10^10≤x1,y1≤10 1 ，修改次数