XOR 합

시간 제한2초메모리 제한256 MB

요약

숫자를 리스트에 삽입하고 각 print 명령마다 가장 큰 K개 수의 XOR을 출력합니다.

문제

비어 있는 수 리스트가 하나 있다. 이 리스트에 $Q$ 개의 명령을 주어진 순서대로 처리한다.

insert N: 리스트에 $N$ 을 넣는다. 같은 수가 여러 번 들어올 수 있다.
print: 리스트에 있는 수 가운데 큰 것부터 $K$ 개를 골라 XOR 합을 출력한다. 리스트에 든 수가 $K$ 개보다 적으면 리스트에 있는 모든 수의 XOR 합을 출력하고, 리스트가 비어 있으면 $0$ 을 출력한다.

XOR 합은 고른 수를 전부 XOR 한 값이다. 두 정수의 XOR는 대부분의 언어에서 ^ 연산자로 계산한다. 하스켈에서는 xor를 쓴다.

값이 같은 수가 여러 개 있으면 각각을 별개의 원소로 센다. 리스트가 $[5, 5, 3]$ 이고 $K = 2$ 이면 고르는 수는 $5$ 와 $5$ 이므로 XOR 합은 $0$ 이다.

XOR에는 쓸모 있는 성질이 있다. $N \oplus M = X$ 이면 $N = X \oplus M$ 이고 $M = X \oplus N$ 이다.

첫 줄에 테스트 케이스의 수 $T$ ( $1 \le T \le 30$ )가 주어진다.

각 테스트 케이스의 첫 줄에는 $Q$ 와 $K$ ( $1 \le Q, K \le 100\,000$ )가 주어진다. 이어서 $Q$ 개의 줄에 명령이 한 줄에 하나씩 주어지며, 각 명령은 다음 두 형태 중 하나이다.

insert N

print

$N$ 은 $2^{31}$ 보다 작은 음이 아닌 정수이다.

print 명령마다 답을 한 줄에 하나씩 출력한다. 리스트는 테스트 케이스마다 비어 있는 상태에서 다시 시작한다.

예제 1

입력

1
5 2
insert 1
insert 2
print
insert 3
print

예상 출력

3
1

예제 2

입력

1
6 3
print
insert 7
print
insert 7
print
print

예상 출력