XOR 자료구조

Albert는 최근 (2진수) XOR 연산과 자료구조에 푹 빠져 있다.

Albert는 XOR에 관련된 여러 연산을 효율적으로 처리하는 자료구조를 만들려고 한다.

처음에는 n개의 정수를 담은 집합 $S_0$으로 자료구조를 초기화하고, 이후 q개의 연산을 수행하면서 각 연산의 결과를 출력해야 한다.

각 연산은 아래 다섯 가지 중 하나이며, 일부 연산은 자료구조에 저장된 정수 집합에 새 정수를 추가하거나 정수를 삭제한다. 따라서 그 뒤의 연산도 영향을 받는다.

1. find_min(v): 현재 자료구조에 저장된 정수 집합이 S라면, (v XOR s) 값이 최소가 되는 S의 원소 s를 찾아 (v XOR s) 값을 출력한다. S는 바뀌지 않는다.
2. find_max(v): 현재 자료구조에 저장된 정수 집합이 S라면, (v XOR s) 값이 최대가 되는 S의 원소 s를 찾아 (v XOR s) 값을 출력한다. S는 바뀌지 않는다.
3. add(v): 현재 자료구조에 저장된 정수 집합 S에 v를 추가한다. 추가한 뒤, S에 저장된 고유한 정수의 개수를 출력한다.
4. remove_min(): 현재 자료구조에 저장된 정수 집합 S의 원소 중 가장 작은 수를 출력한 뒤 삭제한다. 가장 작은 수가 여럿이라면 모두 삭제한다.
5. remove_max(): 현재 자료구조에 저장된 정수 집합 S의 원소 중 가장 큰 수를 출력한 뒤 삭제한다. 가장 큰 수가 여럿이라면 모두 삭제한다.

예를 들어 $S_0 = \{1, 1, 3, 3\}$이고 아래 순서로 총 q = 7개의 연산을 적용한다고 하자.

1. find_min(2): (1 XOR 2) = 3이고 (2 XOR 3) = 1이므로 1을 출력해야 한다. 연산을 적용한 뒤 S는 바뀌지 않으므로 S = {1, 1, 3, 3}이다.
2. find_max(2): (1 XOR 2) = 3이고 (2 XOR 3) = 1이므로 3을 출력해야 한다. 연산을 적용한 뒤 S는 바뀌지 않으므로 S = {1, 1, 3, 3}이다.
3. add(2): S에 새 원소를 추가하여 S = {1, 1, 2, 3, 3}이 된다. 중복을 제외하면 고유한 정수가 모두 3개이므로 3을 출력한다.
4. remove_min(): S의 원소 중 가장 작은 수는 1이므로 1을 출력하고 모두 삭제한다. 연산을 적용한 뒤 S = {2, 3, 3}이다.
5. remove_max(): S의 원소 중 가장 큰 수는 3이므로 3을 출력하고 모두 삭제한다. 연산을 적용한 뒤 S = {2}이다.
6. find_min(2): (2 XOR 2) = 0이므로 0을 출력해야 한다.
7. find_max(2): (2 XOR 2) = 0이므로 0을 출력해야 한다.

위 예제의 올바른 결과는 연산을 적용한 순서대로 [1, 3, 3, 1, 3, 0, 0]이다.

입력으로 n, $S_0$, q, 그리고 q개의 연산을 받아, 각 연산을 적용한 뒤 얻은 결과 q개를 출력하는 프로그램을 작성하시오.

첫 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스의 첫 줄에는 n과 q가 공백으로 구분되어 주어진다.

둘째 줄에는 집합 $S_0$에 포함된 n개의 정수가 공백으로 구분되어 주어진다.

다음 q줄에 걸쳐 각 줄에 하나의 연산이 주어진다.

각 줄에는 1개 혹은 2개의 정수가 공백으로 구분되어 주어지는데, 첫 수는 연산의 종류를 나타내며 {1, 2, 3, 4, 5} 중 하나이다.

문제 본문에서 설명한 대로, 1은 find_min, 2는 find_max, 3은 add, 4는 remove_min, 5는 remove_max 연산을 나타낸다.

연산 1, 2, 3의 경우에만 같은 줄에 두 번째 정수 v가 주어진다.

각 연산을 적용한 뒤 자료구조가 출력해야 하는 값을 한 줄에 하나씩 출력한다.

• 1 ≤ T ≤ 10
• 1 ≤ n, q ≤ 50,000
• 연산과 함께 주어지는 모든 값 v에 대해 0 ≤ v < $2^{25}$
• $S_0$에 주어진 모든 원소 s에 대해 0 ≤ s < $2^{25}$
• 모든 연산에 대하여, 각 연산을 처리하기 전이나 후에 S의 원소가 없는 경우는 입력으로 주어지지 않는다.