mzf的考验

$mzf$立志要成为一个豪杰，当然，他也是一个$OIer$。 他希望自己除了会$OI$之外还会各种东西，比如心理学、吉他、把妹等等。 为了让自己有更大的魅力，他不驼背，不熬夜，整天锻炼，双目炯炯有神，是我们机房最不像$OIer$的人。 然而，在与我们格格不入若干天并且将《易经》研究透彻之后，承受不住我们对他另类的言论，他爆发了。 机房在那一刹那仿佛天塌地陷，世界末日。

八卦有乾、坤、震、巽、坎、离、艮、兑； 两两组合，一上一下，形成了六十四卦，每卦六爻，一共三百八十四爻。 爻分阴阳，阳爻性属阳刚，阴爻性属阴柔。天下之大，无奇不有。千奇百怪，皆出此处。 $mzf$研究透彻了易经之后，画出了$n$个奇怪的图案。他说那是他改进出来的更强大的卜卦体系。 每一个图案有二十行，每一行要么是阴爻$(0)$，要么是阳爻$(1)$，作为一个$OIer$，我们可以将卦象看成一个个二进制串； 他将$n$个图案画在了符纸上，然后进行$m$次操作： 操作1：翻转区间$[l,r]$的图案，比如$(3,1,2,5)$变成$(5,2,1,3)$； 操作2：$mzf$画地为卦，将$[l,r]$之间的卦象都异或上新画的那个卦象； 操作3：$mzf$会询问机房里的其他人$[l,r]$之间卦象代表的二进制数权值和。 如果不能正确回答每个操作$3$，那么机房风水格局将会改变，我们都将...！ 由于$mzf$疯狂之下将我们都捆♂绑♂了起来，所以只能求求你来帮我们解决这个问题。

第一行两个正整数：$n$，$m$（$n$为序列长度，$m$为操作个数） 第二行$n$个正整数：$a[i]$ (用$10$进制数表示每个卦象)$(1<=i<=n)$ 接下来$m$行：每行首先一个正整数$opt$表示操作类型 1. $opt=1$：两个正整数：$l,r$。请翻转区间 $[l,r]$； 2. $opt=2$：三个正整数：$l,r,d$。请将区间$[l,r]$中的所有卦象都异或卦象$d$。（$0\le d\lt 2^{20}$） 3. $opt=3$：两个正整数：$l,r$。请查询区间 $[l,r]$ 的卦象权值和。

对于每个 $opt=3$ 的情况，输出一行答案。

8 9
4 6 2 1 7 9 10 2
1 1 4
3 1 6
2 4 5 2
3 1 6
2 1 5 8
3 1 6
2 5 7 10
3 4 7
3 1 8

29
29
69
24
59

对于 $20\%$ 的数据，$n\le1000$，$m\le 1000$。 对于另外 $20\%$ 的数据，不存在操作 $1$。 对于另外 $20\%$ 的数据，保证 $n$ 为 $2$ 的次幂，且在操作 $1$ 中，保证 $l=i\times(2^j)+1$，$r=(i+1)\times(2^j)$，其中 $i,j$ 为任意值。 对于 $100\%$ 的数据，$n\le 10^5$，$m\le 5\times 10^4$，$1\le l\le r\le n$，$0\le d<2^{20}$。