Background

$mzf$ is determined to become a hero. Of course, he is also an $OIer$. He hopes that besides being good at $OI$, he can also do many other things, such as psychology, guitar, flirting, and so on. To be more attractive, he does not hunch his back, does not stay up late, works out all day, and has bright eyes. He is the least like an $OIer$ in our computer room. However, after being out of place with us for several days and thoroughly studying the I Ching, he could not stand our weird comments about him, and he exploded. At that moment, it felt like the sky was falling and the earth was collapsing. It was like the end of the world.

Problem Description

The Eight Trigrams are Qian, Kun, Zhen, Xun, Kan, Li, Gen, and Dui. Combining them in pairs, one on top and one below, forms the sixty-four hexagrams. Each hexagram has six lines, making a total of 384 lines. Lines are divided into yin and yang. A yang line is strong, and a yin line is soft. The world is vast, and anything can happen. All kinds of strange things come from here. After thoroughly studying the I Ching, $mzf$ drew $n$ strange patterns. He said they were a stronger divination system improved by him. Each pattern has 20 rows. Each row is either a yin line $(0)$ or a yang line $(1)$. As $OIers$, we can view each hexagram as a binary string. He drew these $n$ patterns on talismans, and then performed $m$ operations:

Operation 1: Reverse the patterns in interval $[l,r]$, for example, $(3,1,2,5)$ becomes $(5,2,1,3)$.

Operation 2: $mzf$ draws a new hexagram, and XORs all hexagrams in $[l,r]$ with this newly drawn hexagram.

Operation 3: $mzf$ asks other people in the computer room for the sum of the weights (values) of the binary numbers represented by the hexagrams in $[l,r]$.

If we cannot correctly answer every Operation $3$, then the feng shui layout of the computer room will change, and we will all...!

Since $mzf$, in his madness, tied us all up, we can only beg you to help us solve this problem.

Input Format

The first line contains two positive integers: $n$, $m$ ($n$ is the length of the sequence, and $m$ is the number of operations).

The second line contains $n$ positive integers: $a[i]$ (each hexagram is given in decimal)$(1<=i<=n)$.

Next $m$ lines: each line starts with a positive integer $opt$ indicating the operation type.

1. $opt=1$: two positive integers: $l,r$. Please reverse interval $[l,r]$.
2. $opt=2$: three positive integers: $l,r,d$. Please XOR every hexagram in $[l,r]$ with hexagram $d$. ($0\le d\lt 2^{20}$)
3. $opt=3$: two positive integers: $l,r$. Please query the sum of hexagram weights in interval $[l,r]$.

Output Format

For each case of $opt=3$, output one line with the answer.

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

Hint

For $20\%$ of the testdata, $n\le1000$, $m\le 1000$.

For another $20\%$ of the testdata, there is no Operation $1$.

For another $20\%$ of the testdata, it is guaranteed that $n$ is a power of $2$, and in Operation $1$, it is guaranteed that $l=i\times(2^j)+1$, $r=(i+1)\times(2^j)$, where $i,j$ can be any values.

For $100\%$ of the testdata, $n\le 10^5$, $m\le 5\times 10^4$, $1\le l\le r\le n$, $0\le d<2^{20}$.

Translated by ChatGPT 5