XOR 합 2

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

요약

삽입과 질의가 섞인 명령을 순서대로 처리하며, 저장된 수 중 K번째로 큰 값들의 XOR 합을 출력한다.

난이도: 보통10점 중 7점
유형: 트라이, 비트 연산, 이분 탐색, 정렬
정답자: 아직 제출이 없습니다

문제

수를 담는 리스트가 하나 있다. 리스트는 비어 있는 상태에서 시작하고, 명령 $Q$ 개를 주어진 순서대로 처리한다.

insert N 명령은 리스트에 수 $N$ 을 넣는다. 같은 수가 여러 번 들어올 수 있고, 들어온 횟수만큼 리스트에 남는다.

print K 명령은 리스트에서 가장 큰 수 $K$ 개의 XOR 합을 출력한다. 같은 수가 여러 개 들어 있으면 하나하나를 서로 다른 원소로 센다. 리스트에 있는 수가 $K$ 개보다 적으면 리스트에 있는 모든 수의 XOR 합을 출력하고, 리스트가 비어 있으면 0을 출력한다.

XOR 합은 대상이 되는 수를 모두 XOR 한 결과다. 두 정수의 XOR은 대부분의 언어에서 ^ 연산자로 계산하고, 하스켈에서는 xor를 쓴다. XOR에는 $N \oplus M = X$ 이면 $N = X \oplus M$ 이고 $M = X \oplus N$ 이라는 성질이 있다.

입력

첫 줄에 테스트 케이스의 개수 $T$ ( $1 \le T \le 10$ )가 주어진다. 각 테스트 케이스의 첫 줄에는 명령의 개수 $Q$ ( $1 \le Q \le 100\,000$ )가 주어지고, 이어지는 $Q$ 개의 줄에 명령이 한 줄에 하나씩 주어진다.

명령은 다음 두 형태 중 하나다.

insert N

print K

$N$ 은 $2^{31}$ 보다 작은 음이 아닌 정수이고, $K$ 는 $Q$ 보다 작은 양의 정수다.

출력

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

예제6

예제 1

입력

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

예상 출력

3
1

예제 2

입력

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

예상 출력

예제 3

입력

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

예상 출력

예제 4

입력

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

예상 출력

예제 5

입력

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

예상 출력

30
3
1

예제 6

입력

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

예상 출력