34084번 - D메일 인터랙티브

문제

엘 프사이 콩그루.

— 호오인 쿄우마

이 문제는 인터랙티브 문제이다.

세계선이란 특정 시점의 작은 사건 차이로 갈라진 독립적 차원의 한 갈래를 가리킨다. 이러한 세계선들은 모두 동시에 공존하며 서로 영향을 주지 않는 독립적인 평행 우주라고 볼 수 있다.

세계선은 총 2ドル^N$개가 있으며 각 세계선은 0ドル$ 이상 2ドル^N-1$ 이하의 서로 다른 정수로 나타낼 수 있다. 하지만 당신은 현재 당신이 있는 세계선이 몇 번 세계선인지 모른다. 이를 알아내기 위해 D메일과 다이버전스 미터를 사용하려고 한다.

D메일은 과거로 보낼 수 있는 문자메시지이다. 당신은 D메일로 0ドル$ 이상 2ドル^N-1$ 이하인 정수 $a$를 하나 과거로 보낼 수 있다. 번호가 $x$인 세계선에서 D메일로 정수 $a$를 보내면 과거의 사건이 미세하게 변경되어 $x\oplus a$번 세계선으로 이동하게 된다. ($\oplus$는 비트 XOR 연산자이다.)

다이버전스 미터는 현재 세계선을 나타내는 기계이다. 그러나 이 기계는 세계선을 정확하게 보여주지 못하고 0ドル$ 또는 1ドル$로만 표현할 수 있다. 0ドル\leq i \leq 2^N-1$인 모든 정수 $i$에 대해 다이버전스 미터가 $i$번 세계선에서 출력하는 값을 $f(i)$라고 하자. 당신은 첫 번째 D메일을 보내기 전, 0ドル\leq i \leq 2^N-1$인 모든 정수 $i$에 대해 $f(i)$의 값을 정할 수 있다. $f(i)$의 값은 한 번 정하고 나면 다시 바꿀 수 없으며, 이후 D메일을 보내 세계선이 바뀔 때마다 다이버전스 미터에 출력된 값을 확인할 수 있다. 다이버전스 미터를 설정한 후 D메일을 $N+1$번 이하로 보내 초기의 세계선이 몇 번 세계선이었는지 알아내 보자.

입력

출력

제한

인터랙션

각 입력은 $T$개의 테스트 케이스로 이뤄져 있다. 모든 테스트 케이스에서 $N$의 값과 다이버전스 미터의 설정값은 같다. 즉, 모든 테스트 케이스를 통틀어 $N$의 값과 다이버전스 미터의 설정값은 한 번만 출력한다.

첫째 줄에 $N,ドル $T$의 값이 공백으로 구분되어 주어진다. $(2\leq N \leq 20; 1\leq T \leq 1 ,円 000)$

이후 다이버전스 미터의 설정값을 나타내는 길이가 2ドル^N$인 이진수열을 공백 없이 출력한다. 1ドル\leq i \leq 2^N$인 모든 정수 $i$에 대해 이진수열의 $i$번째 값은 $i-1$번 세계선에서 다이버전스 미터가 출력할 수, 즉 $f(i-1)$의 값을 나타낸다.

이제 당신은 $T$개의 테스트 케이스를 처리해야 한다. 각 테스트 케이스마다 당신은 다음과 같은 방식으로 채점 시스템과 인터랙션 할 수 있다.

• $? ,円 a$:
  • D메일로 정수 $a$를 보낸다. 이후 다이버전스 미터에 출력된 값이 다음 줄에 입력된다. $(0 \leq a \leq 2^N-1)$
  • 이 연산은 각 테스트 케이스마다 최대 $N+1$번 할 수 있다.
• $! ,円 a$:
  • 초기의 세계선이 $a$임을 알아냈다면 이 연산을 통해 답을 제출한다. $(0 \leq a \leq 2^N-1)$
  • 답이 맞았다면 다음 테스트 케이스가 시작된다. 틀렸다면 인터랙션이 종료되고 틀렸습니다를 받게 된다.

각 줄을 출력 후 표준 출력 버퍼를 flush 해줘야 한다. 언어 별로 표준 출력 버퍼를 flush 하는 방법은 다음과 같다. 기타 언어의 경우 각 언어의 documentation을 참조하라.

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

이 문제의 인터랙터는 비적응적이다. 즉, 모든 테스트 케이스에서 초기의 세계선은 미리 정해져있다.

힌트