很久以前，在 Bitworld 的土地上，有一面魔镜。每当你看着它时，数组元素的索引 $i$ 就会被反射为 $i \oplus k$，其中 $k$ 是某个魔钥。拥有这面镜子的巫师喜欢玩序列：有时他会使用异或（XOR）来镜像序列的一部分，有时他会询问区间的加权和。

现在，巫师给你 $T$ 个序列以及针对每个序列的一系列操作。你的任务是处理它们并报告他的查询结果。

你被给定一个长度为 $N$ 的初始序列 $A_0, A_1, \dots, A_{N-1}$。值 $N$ 总是 $2$ 的幂，且满足 $N \le 2^{18}$。

有两种类型的操作：

• 操作类型 1：给定整数 $(l, r, k)$，对于每个 $i \in [l, r)$，设 $$B_i = A_{i \oplus k}$$ 然后对于所有 $i \in [l, r)$，赋值 $A_i = B_i$。
• 操作类型 2：给定整数 $(l, r)$，输出 $$\sum_{i=l}^{r-1} A_i$$

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 2 \times 10^5$) —— 测试用例的数量。

每个测试用例的格式如下：

一行为两个整数 $N$ ($1 \le N \le 2^{18}$，且 $N$ 是 $2$ 的幂) 和 $Q$ ($1 \le Q \le 2 \times 10^5$) —— 序列的长度和操作的数量。

一行为 $N$ 个整数 $A_0, A_1, \dots, A_{N-1}$ ($1 \le A_i \le 1048576$) —— 初始序列。

接下来的 $Q$ 行，每行描述一个操作。

所有操作都在左闭右开区间 $[l, r)$ 上进行，其中 $0 \le l < r \le N$。格式为：

• 1 l r k —— 对区间 $[l, r)$ 应用操作类型 1，参数为 $k$ ($0 \le k < N$)。
• 2 l r —— 对区间 $[l, r)$ 应用操作类型 2。

保证所有测试用例中 $\sum N \le 2^{18}$，$\sum Q \le 2 \times 10^5$。

输出格式

对于每个操作类型 2，在单独的一行中输出结果。

样例

输入样例 1

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

输出样例 1

23
10
1
13
22