给定一个包含 $n$ 个整数的数组 $A$。数组的所有元素从 $1$ 到 $n$ 编号。你的任务是处理 $m$ 个查询。每个查询属于以下类型之一：

1. 在数组 $A$ 的末尾追加整数 $x_j$。
2. 输出 $\sum_{i=l_j}^{r_j} A_i$ 的值（其中 $l_j \le r_j$）。
3. 对数组 $A$ 中的每个元素执行 $A_i = A_i \oplus x_j$。表达式 $A_i \oplus x_j$ 表示对数字 $A_i$ 和 $x_j$ 进行按位异或运算。
4. 对数组 $A$ 进行排序。

你的任务是实现一个合适的数据结构来处理给定数组 $A$ 的 $m$ 个查询。

输入格式

第一行包含一个整数 $n$ —— 数组 $A$ 的初始大小 ($1 \le n \le 2 \cdot 10^5$)。 第二行包含 $n$ 个非负整数 $A_i$ —— 数组 $A$ 的元素 ($0 \le A_i \le 10^9$)。 第三行包含一个整数 $m$ —— 查询的数量 ($1 \le m \le 2 \cdot 10^5$)。 接下来的每一行包含一个查询，格式如下：

• 第一类查询：1 xj
• 第二类查询：2 lj rj
• 第三类查询：3 xj
• 第四类查询：4

对于第一类或第三类查询，$0 \le x_j \le 10^9$。对于第二类查询，$l_j$ 和 $r_j$ 不会超出数组 $A$ 的边界。 你可以假设每个测试用例中至少有一个第二类查询。

输出格式

对于每个第二类查询，在单独的一行中输出其计算出的总和。

样例

输入 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