The Jet-Black Wings

Time limit3sMemory limit512 MB

Summary

Maintain a multiset under global XOR updates and queries asking for the sum of the K smallest elements.

Level: Hard8 of 10
Topics: Trie, Bit manipulation, Divide and conquer, Implementation
Solved: No attempts yet

Problem

"AHHHHHHHHH..."

Eddy, who calls himself the Jet-Black Wings, was fighting an evil organization named Dark Reunion. Then he woke up with a start. It was a dream.

"I must be more powerful." Eddy said to himself.

Eddy trains often to become a powerful fighter. During his training he collected $N$ magic stones. The $i$ -th stone holds $A_i$ units of dark force. Eddy takes $Q$ turns, and on each turn he chooses one of two actions.

1 X: Use $X$ units of dark force on every magic stone. The dark force of each stone becomes the bitwise exclusive or of its current value and $X$ , so a stone holding $A_i$ comes to hold $A_i \oplus X$ .
2 K: Sort all magic stones by dark force in increasing order, then add up the dark force of the first $K$ stones. This turn does not change the dark force of any stone.

Help Eddy check whether his numbers are right.

$x \oplus y$ is the result of applying the bitwise exclusive or operation to the integers $x$ and $y$ . Every modern programming language provides this operation. C++ and Java write it as ^, and Pascal writes it as xor.

Input

The first line contains a single integer $T$ , the number of test cases.

The first line of each test case contains two integers $N$ and $Q$ , the number of magic stones and the number of instructions.

The second line of each test case contains $N$ integers $A_1, A_2, \dots, A_N$ , where $A_i$ is the dark force of the $i$ -th magic stone.

Each of the following $Q$ lines contains one instruction, either 1 X or 2 K.

You may assume:

$T \le 1000$
$1 \le N, Q \le 100000$
$0 \le A_i, X < 2^{31}$
$1 \le K \le N$
At most 5 test cases have $N + Q > 200$ .

Output

For each 2 K instruction, print on its own line the sum of the dark force of the first $K$ magic stones after sorting.

Examples7

Example 1

Input

Expected output

17
7
3

Example 2

Input

1
1 4
2147483647
2 1
1 2147483647
2 1
2 1

Expected output

2147483647
0
0

Example 3

Input

1
5 6
0 0 0 0 0
2 5
1 1073741824
2 3
2 5
1 1073741824
2 5

Expected output

Example 4

Input

1
100 5
2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483647 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646 2147483646
2 100
1 1
2 100
1 2147483647
2 100

Expected output

214748364650
214748364650
50

Example 5

Input

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

Expected output

Example 6

Input

Expected output

Example 7

Input

1
5 8
10 20 30 40 50
2 5
1 123456789
2 5
2 2
1 123456789
2 5
2 2
2 3

Expected output