P11071 "QMSOI R1" Distorted Fate

 **O Fortuna velut luna statu variabilis……** (Image from Phigros artwork. Please contact for removal if needed.) Enhanced version of [T512613](https://www.luogu.com.cn/problem/T512613).

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: $$ \sum_{i=l}^r f(A[l,i]) $$ 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: $$(\sum_{i=l}^r\bigcup_{j=l}^i A_j) \bmod 2^{30}$$ where $\bigcup$ denotes bitwise OR.

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.

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

## 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: | Subtask | $n$ | $q$ | Time | Memory | Score | | :----------: | :----------: | :----------: | :----------: | :----------: |:----------:| | $0$ | $\le 100$ | $\le 100$ | $1s$ | $512MB$ | $20$ | | $1$ | $\le 2\times 10^4$ | $\le 2\times 10^4$ | $1s$ | $512MB$ | $20$ | | $2$ | $\le 2\times 10^5$ | $\le 2\times 10^5$ | $3s$ | $512MB$ | $20$ | | $3$ | $\le 2\times 10^5$ | $\le 2\times 10^5$ | $3s$ | $\color{red}100MB$ | $40$ | 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