Source: Super League of Chinese College Students Algorithm Design 2022, Contest 2 by HDU.

Problem Description

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.

Input

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$.

Output

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

Sample

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 \oplus 4 = 6$.