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