34883번 - XOR 계산 컴퓨터와 메모리 인터랙티브투 스텝

문제

이 문제는 투 스텝 인터랙티브 문제입니다.

준혁이는 길이 $N$의 수열 $A$와 정수 $Q$에 대해 $\max(A_i \oplus Q)$를 구하는 컴퓨터를 만들었다.

두 정수 $a,ドル $b$에 대해 $a \oplus b$는 $a$와 $b$를 XOR한 값으로 정의한다.

준혁이는 두 단계로 컴퓨터를 사용해 최대 XOR을 구한다.

• 첫 번째 단계에서는 $N$과 수열 $A$를 입력받으며, 두 번째 단계에 사용할 길이 $X$의 비트 배열인 메모리 $M$을 만든다.
• 두 번째 단계에서는 $M$을 특수 슬롯에 장착하고 $Q$를 입력받으며, $M$에 $Y$회 접근하여 답을 구한다.

준혁이의 컴퓨터가 질투 났던 현중이는 첫 번째 단계가 끝난 후 준혁이의 연구소로 가서 몰래 메모리의 2ドル$개의 비트를 손상시키는 계획을 세웠다. 손상된 비트는 0이나 1이 아닌 -1로 표현되며, 손상되기 이전 비트를 복원할 수 없다.

현중이의 계획을 간파한 당신은 첫 번째 단계 이후 비트가 2ドル$개 손상될 때 두 번째 단계에서 올바르게 답을 구할 수 있도록 두 단계의 컴퓨터를 모두 만들어 보자.

단, 자원의 한계로 $X+Y$는 300ドル$을 넘겨서는 안 된다.

입력

당신의 프로그램은 채점 데이터 하나당 총 두 번 실행된다. 당신은 하나의 소스 코드에 두 가지 실행 과정을 모두 구현해야 한다.

모든 입력의 첫 줄에는 실행 단계를 나타내는 정수 $S$가 주어진다. (1ドル \leq S \leq 2$)

둘째 줄에는 테스트케이스의 개수 $T$가 주어진다. (1ドル \leq T \leq 1,000円$)

만약 $S$가 1ドル$이라면 모든 $T$개의 테스트케이스에 대해 첫 번째 단계를 수행해야 하고, $S$가 2ドル$라면 모든 $T$개의 테스트케이스에 대해 두 번째 단계를 수행해야 한다.

출력

제한

첫 번째 단계

입력

각 테스트케이스는 두 줄로 이루어져 있다.

테스트케이스의 첫째 줄에 $N$이 주어진다. (2ドル \leq N \leq 15$)

테스트케이스의 둘째 줄에 정수 수열 $A_1, A_2, \ldots, A_N$이 공백으로 구분되어 주어진다. (0ドル \le A_i \le 4,095円$)

출력

테스트케이스의 첫째 줄에 비트 메모리 $M$의 길이 $X$를 출력한다. (2ドル \leq X \leq 300$)

테스트케이스의 둘째 줄에 비트 메모리 $M_1, M_2, \ldots M_X$를 공백으로 구분하여 출력한다.

두 번째 단계

입력

각 테스트케이스는 한 줄로 이루어져 있다.

테스트케이스의 첫째 줄에 첫 번째 단계에서 출력한 메모리의 크기 $X$와 $Q$가 공백으로 구분되어 주어진다. (0ドル \le Q \le 4,095円$)

이후 채점 시스템과의 인터랙션이 시작된다.

인터랙션

당신은 표준 출력에 다음 연산을 각 줄에 출력하는 것으로, 채점 시스템과 인터랙션할 수 있다. 각 토큰은 공백으로 구분하며, 각 연산의 끝에 개행문자를 출력하여야 한다.

당신은 정답을 구하기 위해 채점 시스템에게 다음과 같은 연산을 할 수 있다.

• ? $i$: 첫 번째 단계에서 출력한 $M_i$의 값을 읽는다.
  • 다음 줄에 $M_i$의 값이 다음 줄에 입력으로 주어진다.
  • 만약 $i$번째 메모리가 손상되었다면, $M_i$의 값 대신 $-1$이 입력된다.
  • 1ドル \le i \le X$

? 연산을 사용한 횟수를 $Y$라고 할 때 $X+Y$는 300ドル$을 초과하지 않아야 한다.

정답을 알아냈다면 다음과 연산을 통해 정답을 제출한다.:

• ! $x$: 모든 1ドル \le i \le N$에 대해 $\max(A_i \oplus Q)$의 값이 $x$임을 제출한다.

정답 제출 연산 이후에는 다음 테스트케이스가 시작되며 마지막 테스트케이스의 정답을 제출 한 이후에는 프로그램을 종료한다.

만약 연산이 잘못된 출력이거나 제한을 초과하였다면 당신은 -2를 다음 줄에 입력받으며 이 입력이 주어질 경우 프로그램을 즉시 종료해야 한다.

채점 시스템은 적응적이지 않다. 즉 첫 번째 단계 이후 손상된 메모리는 결정되며 상호작용 도중에 손상된 메모리의 위치를 바꾸지 않는다.

각 연산 이후에는 표준 출력 버퍼를 비워야 한다.

각 언어별로 표준 출력 버퍼를 비우는 방법은 다음과 같다. 기타 언어의 경우, 언어의 레퍼런스 페이지를 참조하여라.

• C: fflush(stdout)
• C++: std::cout << std::flush
• Java, Kotlin: System.out.flush()
• Python: sys.stdout.flush()

노트