小 N 最近在做关于树的题。今天她想了这样一道题，给定一棵 个节点的树，节点按 编号，一开始每个节点上的权值都是 ，接下来有 个操作。第一种操作是修改，给出 个整数 ，对于 到 路径上加上一个首项是 ，公差是 的等差数列，因为小 N 十分谨慎，所以她每做完一个修改操作就会保存一次，初始状态是第 次保存的局面。第二种操作是求和，给出 个整数 ，输出 到 路径上所有节点的权值和。第三种操作是读取之前第 次保存的局面，所有节点的状态回到之前第 次保存的状态。现在请你对每一个求和操作输出答案。
第一行两个整数 表示节点个数和操作次数。
接下来 行每行 个整数 表示了这棵树中 和 这 个节点间有边相连。
接下来 行每行先有一个字符表示了操作的类型；同时为了保证在线，我们设 表示上一次输出的答案：
c
q
l
对于每一个求和操作，输出求和后的值。
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
持久化线段树
