Background

O Fortuna velut luna statu variabilis……

(Image from Phigros artwork. Please contact for removal if needed.)

Enhanced version of T512613.

Problem Description

Geopelia needs to capture a special kind of gravitational wave, different from a black hole.

The $i$-th gravitational wave has a frequency $A_i$. Multiple gravitational waves will affect each other and stack together, forming a gravitational wave with a faster frequency.

Specifically, for a sequence $A$ of length $n$, the frequency after stacking all gravitational waves in $A$ is $f(A)=\bigcup\limits_{i=1}^n A_i$, where $\bigcup$ denotes bitwise OR.

Now, Geopelia needs to know the sum of frequencies of several intervals that start from the same gravitational wave.

That is, Geopelia asks you for the value of:

where $A[l,r]$ is the sequence formed by $A_l,A_{l+1},\cdots,A_{r-1},A_r$.

Unfortunately, due to the gravitational influence of the Azure Boundary, in some interval $[l,r]$, the frequencies of all gravitational waves might be XORed with a value $x$.

Geopelia wants to update her data in real time. Can you help her?

She knows the frequencies may be very large, so you only need to tell her the answer $\bmod \ 2^{30}$.

Formal Statement

Given an array $A$ of length $n$, you need to perform the following $q$ operations.

1. 1 l r x XOR $A_i$ with $x$ for all $l\le i\le r$.

2. 2 l r Compute:

where $\bigcup$ denotes bitwise OR.

Input Format

The first line contains two integers $n$ and $q$, representing the number of gravitational waves and the number of operations.

The second line contains $n$ integers. The $i$-th integer is the initial frequency $A_i$ of gravitational wave $i$.

Then follow $q$ lines. Each line contains three integers $opt,l,r$.

If $opt=1$, an additional integer $x$ is given, meaning to XOR the frequencies in interval $[l,r]$ with $x$.

If $opt=2$, it means this is a query.

Output Format

For each query, output one integer per line, representing the result of the expression $\bmod \ 2^{30}$.

3 3
1 2 3
2 1 3
1 1 2 2
2 1 3

7
9

Hint

Sample Explanation

For the first query: at this time $A=\{1,2,3\}$, so the answer is $1+1\cup 2+1\cup 2\cup 3=1+3+3=7$.

For the second query: at this time $A=\{3,0,3\}$, so the answer is $3+3\cup 0+3\cup 0\cup 3=3+3+3=9$.

Constraints

This problem uses bundled testing with subtasks. The score for each subtask is as follows:

For all testdata, $0\le a_i,x< 2^{30}$, $1\le l\le r\le n$.

INITALIZING……
SCANING……
CONNECTING……__PhigrOS Client Login
TIME_OUT!
CONNECTING……__Unknown
SUCCESS!
————————
……Nine……Bird……
……Dove……!
……Hello?
…Can you hear me?
Dove?![SIGNAL LOST]

Translated by ChatGPT 5