Description

There is an array $A$ of length $n$, indexed starting from $1$. You need to process $m$ operations of the following four types:

1. Append a number $x$ to the end of array $A$.
2. Output $\sum_{i=l}^{r}A_i$.
3. Change every number $A_i$ in array $A$ to $A_i\oplus x$. ($\oplus$ denotes the XOR operation.)
4. Sort array $A$ in non-decreasing order.

Input Format

The first line contains an integer $n$, the initial size of $A$.
The next line contains $n$ non-negative integers $A_i$, representing each element in $A$.
The next line contains an integer $m$, the number of operations.
The next $m$ lines each describe one operation:

• 1 x: the first operation, append $x$ to the end.
• 2 l r: the second operation, query $\sum_{i=l}^{r}A_i$. It is guaranteed that $1\le l\le r\le n'$, where $n'$ is the length of the sequence at the time of the operation.
• 3 x: the third operation, XOR every element with $x$.
• 4: the fourth operation, sort array $A$.

Output Format

For each operation of the second type, output the answer.

5
5 2 6 2 0
5
2 1 5
1 2
3 7
2 2 6
4

15
23

Hint

Idea: WJMZBMR, Solution: WJMZBMR, Code: WJMZBMR, Data: WJMZBMR

$1\le n,\,m\le 10^5, 0\le x,A_i\le 10^9$

Translated by ChatGPT 5