背景

$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\le i\le 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}$。