XOR 자료구조

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

Albert는 XOR에 관련된 여러 가지 연산을 효율적으로 할 수 있는 자료 구조를 만들고 싶다.

처음에는 n개의 정수를 포함한 집합 S0을 이용하여 자료 구조를 초기화 하며, 그 이후 q개의 연산을 수행하여 옳은 답을 출력해야한다.

각 연산은 아래 다섯 가지 중 하나이며, 일부 연산은 자료 구조에 저장된 정수 집합에 새로운 정수를 추가하거나 정수를 지우기도 한다 (따라서 그 이후의 연산은 영향을 받게 된다).

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

예를 들어, S0 = {1,1, 3, 3} 이고 아래와 같은 순서로 총 q = 7개의 연산을 적용한다고 해보자.

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

위의 예제의 경우, 올바른 결과는 (연산 적용 순서대로) [1, 3, 3, 1, 3, 0, 0]이 된다.

입력으로 n, S0, q, 그리고 q개의 연산을 받아 총 q개의 정수 (각 연산을 적용한 후 얻은 결과)를 출력하는 프로그램을 작성하시오.

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

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

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

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

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

문제 본문에 설명된바와 같이, 1은 find_min, 2는 find_max, 3은 add, 4는 remove_min, 그리고 5는 remove_max 연산을 나타낸다.

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

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