Copy

Kayzin has a list of integers, initially the list is $a_1,a_2,\ldots,a_n$. He will execute $q$ operations.

For an operation of first type, he will select an interval $[l_i, r_i]$, copy and insert it to the end of the interval.

For an operation of second type, he wonder the $x_i$-th integer of the list.

You need to print the xor sum of all the answers of second type operations.

ps: What is xor? The xor value of two integers is equal to addition in binary without carry.

ps: $n$ is a constant for each test case.

First line is an integer $T$, indicating the number of test cases. For each test case:

First line is 2 integers $n,q$, indicating the length of initial list and the number of operations.

Next line is $n$ integers $a_1,a_2,\ldots,a_n$, indicating the initial list.

Next $q$ line, one operation per line. The $i$-th line could be 3 integers ($1,l_i,r_i$), indicating the first type operation, or 2 integers ($2,x_i$), indicating the second type operation.

$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,$ the sum of the number of first type operations (all test cases together) not exceeds $20000$.

For each test case, print one line, indicating the xor sum of the answers.

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

6

For first operation, the 4-th integer is 4.
For second operation, $2, 3, 4$ is copied, the list becomes $1,2,3,4,2,3,4,5$.
For third operation, the 5-th integer is 2.
So the result is 2 xor 4 = 6

2022“杭电杯”中国大学生算法设计超级联赛（2）