给定 $2^k$ 个数：$a_0, a_1, \dots, a_{(2^k-1)}$。

定义 $s(x)$ 如下：

$$s(x) = \begin{cases} 0 & \text{若 } x \text{ 的二进制表示中有偶数个 } 1 \\ 1 & \text{否则} \end{cases}$$

你需要支持五种操作：

• 输出 $\text{Xor}_{i=l}^r s(i) a_i = s(l) a_l \text{ xor } s(l+1) a_{l+1} \text{ xor } \dots \text{ xor } s(r) a_r$。
• 将区间 $[l, r]$ 内的每个 $a_i$ 同时赋值为 $a_{(i \text{ xor } x)}$。
• 将区间 $[l, r]$ 内的每个 $a_{(i \text{ xor } x)}$ 同时赋值为 $a_i$。
• 将区间 $[l, r]$ 内的每个 $a_i$ 同时赋值为 $(a_i \text{ xor } x)$。
• 将 $a_x$ 赋值为 $y$。

此处的 Xor 指按位异或运算。在二进制表示中，如果两个操作数在某一位上的位值不同，则结果在该位上为 1，如果相同则为 0。例如： $5 \text{ xor } 3 = 6$，即 $(101)_2 \text{ xor } (011)_2 = (110)_2$。

输入格式

第一行包含一个整数 $T$，表示测试用例的数量。 对于每个测试用例： 第一行包含一个整数 $k$ ($0 \le k \le 17$)。 接下来一行包含 $2^k$ 个整数，第 $i$ 个整数为 $a_{(i-1)}$ ($0 \le a_i < 2^k$)。 接下来一行包含一个整数 $Q$ ($1 \le Q < 2^k$)，表示操作数量。 接下来 $Q$ 行，每行格式为以下之一：

• $1 \ l \ r$：输出 $\text{Xor}_{i=l}^r s(i) a_i$。
• $2 \ x \ l \ r$：将区间 $[l, r]$ 内的每个 $a_i$ 同时赋值为 $a_{(i \text{ xor } x)}$。
• $3 \ x \ l \ r$：将区间 $[l, r]$ 内的每个 $a_{(i \text{ xor } x)}$ 同时赋值为 $a_i$。
• $4 \ x \ l \ r$：将区间 $[l, r]$ 内的每个 $a_i$ 同时赋值为 $(a_i \text{ xor } x)$。
• $5 \ x \ y$：将 $a_x$ 赋值为 $y$。

保证 $0 \le x, y < 2^k$ 且 $0 \le l \le r < 2^k$。

输出格式

对于每个操作 1，输出一行包含一个整数，表示答案。

样例

样例输入 1

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

样例输出 1

0
1
7