所谓的可持久化数据结构，就是保存这个数据结构的所有历史版本。现在你的任务就是要维护一个可持久化数据结构。
有一个长度为n的整数数列A，最初所有元素都为0。还有一个辅助变量C，一开始也是0。现有如下两种操作：
1 i x ：将A[i^C]的值加上x，然后将C设为更改后的A[i^C]的值。
2 l r t: 查询t次操作1之后的[l^C, r^C]的区间和（注意：C是进行此次2询问时的C，而不是t次1操作后的C，用于强制在线），然后将C设为此次询问的答案。保证输入合法。
(其中“^”符号表示异或操作)

第一行两个整数n(1<=n<=1000000), q(1<=q<=100000)，表示数列的长度和询问的个数。
接下来q行，每行为1 i x或2 l r t，含义如上文所说。(x<=1000)

对于每一个操作2，在单独一行输出其答案。