사라진 쓰레기

뒤뜰 대청소가 끝난 뒤 에브스티그라프의 이웃들은 모은 낙엽과 쓰레기를 자루에 담아 밤새 밖에 두었다. 다음 날 아침 쓰레기가 모두 사라졌다. 남은 것은 'УсТнЫй СчЁт 3000'이라고 적힌 이상한 기계뿐이다. 도둑이 남긴 힌트이므로, 이 기계를 먼저 풀어야 도둑에 대한 정보를 얻을 수 있다.

이 기계는 암산 실력을 시험한다. 먼저 배열 $a_1, \ldots, a_n$이 주어지고, 이후 구간 $[l, r]$에 대해 다음 연산 중 하나를 요구한다.

1. $\sum_{i=l}^{r} (a_i \oplus i)$를 구한다. 여기서 $\oplus$는 두 수의 XOR이다.
2. 구간 $[l, r]$의 모든 원소를 $x$로 바꾼다.
3. 구간 $[l, r]$의 모든 원소에 $x$와 비트 단위 AND, OR, XOR 중 하나를 적용한다.

첫 줄에 두 정수 $n$과 $m$이 주어진다. 각각 배열의 원소 개수와 질의 개수이며, $1 \le n, m \le 10^5$이다.

둘째 줄에 $n$개의 정수 $a_1, \ldots, a_n$이 주어진다. $0 \le a_i < 2^{15}$이다.

이어서 $m$개의 줄에 질의가 한 줄씩 주어진다.

• 첫 번째 유형: 1 $l$ $r$
• 두 번째 유형: 2 $l$ $r$ $x$
• 세 번째 유형: 3 $l$ $r$ $x$ $c$. 여기서 $c$는 적용할 연산이며, AND는 &, OR는 |, XOR는 ^ 기호로 나타낸다.

모든 질의에서 $1 \le l \le r \le n$이고 $0 \le x < 2^{15}$이다.

첫 번째 유형의 질의마다 구한 합을 새 줄에 출력한다.