There is an array $A$ of length $n$, with indices starting from $1$. There are $m$ operations to process, which are 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. Replace every element $A_i$ in array $A$ with $A_i \oplus x$ (where $\oplus$ denotes the bitwise XOR operation).
4. Sort the array $A$ in non-decreasing order.

Input

The first line contains an integer $n$, representing 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$, representing the number of operations.

The next $m$ lines each describe an operation:

• 1 x: Perform the first operation, inserting the number $x$ at the end.
• 2 l r: Perform the second operation, querying $\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: Perform the third operation, XORing every number by $x$.
• 4: Perform the fourth operation, sorting the array $A$.

Output

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

Examples

Input 1

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

Output 1

15
23

Note

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

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