Sabbat of the witch
题目背景
您正在在游玩《魔女的夜宴》,突然开始思考一个哲学问题:这作的restart线到底算不算ntr？
~~您在思索了很长时间之后,突然注意到这是个涉及到时间线和人格同一性的哲学问题~~
此时您突然发现galgame和数(毒)据(瘤)结(分)构(块)有一些奥妙重重的关系，为了更好的思考这个问题，您决定去写一道数(毒)据(瘤)结(分)构(块)题
题目描述
维护一个序列,支持以下三种操作
1.区间赋值
2.区间求和
3.撤回之前的一个区间赋值操作
**强制在线**
注意：这里的撤回操作既不会影响之前的操作也不会影响之后的操作，换句话讲撤回一个操作之后序列将会变成历史上从来没有过被撤回操作的状态
煮个栗子，假设我们对序列按顺序执行了1,2,3,4,5号操作
当我们撤回操作4的时候，整个序列应该和按顺序执行了1,2,3,5操作之后的序列一样
当我们接着撤回操作2的时候，整个序列应该和按顺序执行了1,3,5操作之后的序列一样
输入输出格式
输入格式
第一行两个整数$n,m$表示序列长度和操作个数
第二行$n$个整数$a_{1}...a_{n}$其中$a_{i}$表示序列的第$i$项
接下来$m$行
如果这一行是$1,l,r,v$的话代表将$(l,r)$这段区间赋值成$v$,假如这个操作是第$k$次赋值操作，那么这个操作的编号就是$k$
如果这一行是$2,l,r$的话代表询问$(l,r)$这段区间中数字的和
如果这一行是$3,x$的话代表撤回编号为$x$的操作
**数据保证被撤回的操作一定存在并且每个操作只会被撤回一次**
为了体现题目的在线性，我们设lastans表示读入当前操作时最后一次询问的答案，(lastans的初始值为0)
那么对于操作1,你需要操作的真实区间是$(l \oplus lastans,r \oplus lastans)$
对于操作2,你需要询问的真实区间是$(l \oplus lastans,r \oplus lastans)$
对于操作3,你需要撤回的操作编号是$x \oplus lastans$
其中$\oplus$运算符表示异或运算
输出格式
对于每一个操作2输出一行一个整数，表示询问区间中的元素之和
为了方便你理解题意和调试，我们了准备两个样例，一个是强制在线的而另一个是非强制在线的(尽管本题没有非强制在线的部分分)
输入输出样例
输入样例 #1
20 20
8 6 4 9 9 8 5 5 7 9 8 8 5 8 2 2 2 1 9 4
1 17 19 4
1 3 8 5
3 2
2 4 10
1 14 19 8
2 10 16
2 9 9
1 1 18 1
1 1 7 10
2 4 6
2 9 10
1 5 17 2
1 10 19 6
1 2 5 2
1 6 8 2
1 14 19 1
1 4 7 6
1 17 19 10
2 8 12
1 10 10 2
输出样例 #1
52
54
7
30
2
22
输入样例 #2
20 20
8 6 4 9 9 8 5 5 7 9 8 8 5 8 2 2 2 1 9 4
1 17 19 4
1 3 8 5
3 2
2 4 10
1 58 39 8
2 62 36
2 63 63
1 6 21 1
1 6 0 10
2 3 1
2 23 20
1 7 19 2
1 8 17 6
1 0 7 2
1 4 10 2
1 12 17 1
1 6 5 6
1 19 17 10
2 10 14
1 28 28 2
输出样例 #2
52
54
7
30
2
22
说明
对于第9,10个测试点,满足$n,m \leq 10^4$，这两个测试点的分数都为1
对于剩余的测试点$n,m \leq 10^5$并且操作1的个数不超过$65000$
保证输入的数字全部小于$10^9$