Guess the Data Structure

You are given an array $A$ of $n$ integers, numbered from 1 to $n$. Process $m$ queries of the following kinds:

1. Append integer $x_j$ to the end of the array $A$.
2. Output the value of $\sum_{i=l_j}^{r_j} A_i$ ($l_j \leq r_j$).
3. Replace each element $A_i$ with $A_i \oplus x_j$, where $\oplus$ is bitwise XOR.
4. Sort the array $A$.

Implement a data structure that processes these queries.

The first line contains $n$ ($1 \leq n \leq 2 \cdot 10^{5}$), the initial size of $A$. The second line contains $n$ integers $A_i$ ($0 \leq A_i \leq 10^{9}$). The third line contains $m$ ($1 \leq m \leq 2 \cdot 10^{5}$), the number of queries. Each of the next $m$ lines is one query in one of these formats: 1 $x_j$, 2 $l_j$ $r_j$, 3 $x_j$, or 4.

For queries of types 1 and 3, $0 \leq x_j \leq 10^{9}$. For queries of type 2, $l_j$ and $r_j$ are within the bounds of the array. Each test case has at least one query of type 2.

For each query of type 2, output its sum on a separate line.