문제

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

준혁이는 길이 의 수열 와 정수 에 대해 를 구하는 컴퓨터를 만들었다.

두 정수 , 에 대해 는 와 를 XOR한 값으로 정의한다.

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

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

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

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

단, 자원의 한계로 는 을 넘겨서는 안 된다.

입력

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

모든 입력의 첫 줄에는 실행 단계를 나타내는 정수 가 주어진다. ()

둘째 줄에는 테스트케이스의 개수 가 주어진다. ()

만약 가 이라면 모든 개의 테스트케이스에 대해 첫 번째 단계를 수행해야 하고, 가 라면 모든 개의 테스트케이스에 대해 두 번째 단계를 수행하면 된다.

첫 번째 단계

입력

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

테스트케이스의 첫째 줄에 이 주어진다. ()

테스트케이스의 둘째 줄에 정수 수열 이 공백으로 구분되어 주어진다. ()

출력

테스트케이스의 첫째 줄에 비트 메모리 의 길이 를 출력한다. ()

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

두 번째 단계

입력

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

테스트케이스의 첫째 줄에 첫 번째 단계에서 출력한 메모리의 크기 와 가 공백으로 구분되어 주어진다. ()

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

인터랙션

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

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

• ? : 첫 번째 단계에서 출력한 의 값을 읽는다.

*  다음 줄에 $M_i$의 값이 다음 줄에 입력으로 주어진다.

*  만약 $i$번째 메모리가 손상되었다면, $M_i$의 값 대신 $-1$이 입력된다.
*  $1 \le i \le X$

? 연산을 사용한 횟수를 라고 할 때 는 을 초과하지 않아야 한다.

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

• ! : 모든 에 대해 의 값이 임을 제출한다.

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

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

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

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

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

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