XOR Sum 2

Time limit2sMemory limit512 MB

Summary

Process a stream of insertions and queries, printing the XOR of the K largest stored values.

Level: Medium7 of 10
Topics: Trie, Bit manipulation, Binary search, Sorting
Solved: No attempts yet

Problem

You keep one list of numbers. The list starts empty, and you process $Q$ instructions in the order given.

The instruction insert N puts the number $N$ into the list. The same number can arrive several times, and every arrival stays in the list.

The instruction print K prints the XOR sum of the $K$ largest numbers in the list. If a number is present several times, each copy counts as its own element. If the list holds fewer than $K$ numbers, print the XOR sum of every number in the list, and if the list is empty, print 0.

The XOR sum of a group of numbers is the result of XOR-ing all of them. Most languages compute the XOR of two integers with the ^ operator, and Haskell uses xor. XOR has the property that $N \oplus M = X$ implies $N = X \oplus M$ and $M = X \oplus N$ .

Input

The first line contains the number of test cases $T$ ( $1 \le T \le 10$ ). The first line of each test case contains the number of instructions $Q$ ( $1 \le Q \le 100\,000$ ), and the next $Q$ lines contain one instruction each.

Each instruction has one of the two forms below.

insert N

print K

$N$ is a non-negative integer smaller than $2^{31}$ , and $K$ is a positive integer smaller than $Q$ .

Output

For every print instruction, print the answer on its own line. The list starts empty again for each test case.

Examples6

Example 1

Input

1
5
insert 1
insert 2
print 2
insert 3
print 2

Expected output

3
1

Example 2

Input

1
6
print 1
insert 7
print 4
insert 7
print 3
print 1

Expected output

Example 3

Input

1
9
insert 5
insert 5
insert 5
print 1
print 2
print 3
insert 4
print 2
print 4

Expected output

Example 4

Input

1
8
insert 0
insert 2147483647
print 1
print 2
insert 2147483646
print 2
print 3
print 1

Expected output

Example 5

Input

3
3
insert 10
insert 20
print 2
2
insert 3
print 1
4
insert 1
insert 2
insert 3
print 2

Expected output

30
3
1

Example 6

Input

1
20
insert 1
print 1
insert 2
print 2
insert 3
print 3
insert 4
print 4
insert 5
print 5
insert 6
print 6
insert 7
print 7
insert 8
print 8
insert 9
print 9
insert 10
print 10

Expected output