Kayzin 有一个整数列表，初始列表为 $a_1, a_2, \dots, a_n$。他将执行 $q$ 次操作。

对于第一类操作，他会选择一个区间 $[l_i, r_i]$，将其复制并插入到当前列表的末尾。

对于第二类操作，他想知道列表中第 $x_i$ 个整数是多少。

你需要输出所有第二类操作答案的异或和。

注：什么是异或？两个整数的异或值等于二进制下不进位的加法。

输入格式

第一行是一个整数 $T$，表示测试用例的数量。对于每个测试用例：

第一行是 2 个整数 $n, q$，表示初始列表的长度和操作次数。

下一行是 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示初始列表。

接下来 $q$ 行，每行一个操作。第 $i$ 行可能是 3 个整数 $(1, l_i, r_i)$，表示第一类操作；或者是 2 个整数 $(2, x_i)$，表示第二类操作。

$1 \le T \le 10, 1 \le n, q \le 10^5, 1 \le a_i \le 10^9, \sum n \le 10^5, \sum q \le 10^5, 1 \le x_i, l_i, r_i \le n$，第一类操作的数量不超过 $20000$。

输出格式

对于每个测试用例，输出一行，表示答案的异或和。

样例

输入 1

1
5 3
1 2 3 4 5
2 4
1 2 4
2 5

输出 1

6

说明

对于第一次操作，第 4 个整数是 4。 对于第二次操作，复制 $2, 3, 4$，列表变为 $1, 2, 3, 4, 2, 3, 4, 5$。 对于第三次操作，第 5 个整数是 2。 所以结果为 $2 \oplus 4 = 6$。