시간 제한메모리 제한제출정답맞힌 사람정답 비율
5 초 256 MB43337.500%

문제

You are given an array $A$ consisting of $n$ integers. All its elements are numbered with consecutive integers from $1$ to $n$. Your task is to process $m$ queries. Each of these queries is one 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. Perform $A_{i} = A_{i} \oplus x_{j}$ for each element of the array $A$. Expression $A_{i} \oplus x_{j}$ means applying the operation of bitwise exclusive "OR" to numbers $A_{i}$ and $x_{j}$.
  4. Sort the array $A$.

Your task is to implement a proper data structure to process $m$ given queries for a given array $A$.

입력

First line of input contains the only integer $n$ --- the initial size of the array $A$ ($1 \leq n \leq 2 \cdot 10^{5}$).

Second line of input contains $n$ non-negative integers $A_{i}$ --- elements of the array $A$ ($0 \leq A_{i} \leq 10^{9}$).

Third line of input contains the only integer $m$ --- the number of queries ($1 \leq m \leq 2 \cdot 10^{5}$).

Each of the following lines contains a separate query in the following format:

  • For the first kind of query:  "$1$ $x_{j}$"
  • For the second kind of query:  "$2$ $l_{j}$ $r_{j}$"
  • For the third kind of query:  "$3$ $x_{j}$"
  • For the fourth kind of query:  "$4$"

For any query of the first or the third kind $0 \leq x_{j} \leq 10^{9}$. For any query of the second kind $l_{j}$ and $r_{j}$ do not violate bounds of the array $A$.

You may assume that at least one query in each test case is of the second kind.

출력

For each query of the second kind output its resulting sum on a separate line.

예제 입력 1

5
3 4 7 3 6
7
3 5
2 2 4
4
1 15
2 3 6
3 1
2 1 6

예제 출력 1

9
30
33