34844번 - 인터랙티브 XOR 게임 인터랙티브

문제

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

한양대학교의 KIZIN LAB에서 2025년에 발매한 게임 "인터랙티브 XOR 게임"의 규칙은 다음과 같다.

게임을 시작하기 전, 당신은 누가 선공으로 플레이할지와 게임의 승점을 어떻게 계산할지 결정한다. 승점을 계산하는 방식은 아래에서 설명한다.

• 선공부터 시작하여 선공과 후공이 번갈아가며 차례를 가진다.
• 게임을 시작할 때 0ドル$부터 1023ドル$까지의 정수가 하나씩 적힌 1024ドル$장의 카드를 나열한다.
• 자신의 차례에는 아무도 가져가지 않은 카드 중 하나를 가져가야 한다. 무슨 카드를 가져가는지는 상대에게도 보인다.
• 선공과 후공이 각각 $N$장의 카드를 가져가면 게임이 종료되며 승점 계산이 시작된다.

승점은 max와 min이라는 두 가지 방법으로 계산할 수 있다.

두 플레이어가 가져간 2ドルN$장의 카드에 적힌 값을 모두 XOR한 값을 $T$라고 하자. 승점 계산 방식이 max라면 승점은 $T$이고, 승점 계산 방식이 min이라면 승점은 1023ドル-T$이다.

당신은 채점 프로그램과 "인터랙티브 XOR 게임"을 플레이해야 한다.

당신은 당신이 얻을 수 있는 최대 승점을 얻도록 누가 선공으로 플레이할지와 승점을 어떻게 계산할지를 정한 후, 얻을 수 있는 최대 승점을 얻어야 한다.

인터랙션

첫째 줄에 한 플레이어가 가져갈 수 있는 카드의 수 $N$이 주어진다. (1ドル\leq N\leq 512$)

당신은 이를 읽고 첫째 줄에 당신이 선공으로 플레이하겠다면 first를, 후공으로 플레이하겠다면 second를 출력한 뒤, 게임의 승점 계산 방식인 max또는 min을 공백으로 구분하여 출력해야 한다.

이후 채점 프로그램과의 게임이 진행된다.

당신의 차례일 때는 당신은 당신이 가져갈 카드에 적힌 정수 $x$를 출력해야 한다.

채점 프로그램의 차례일 때는 채점 프로그램이 가져간 카드에 적힌 정수 $x$가 입력으로 주어진다. 채점 프로그램은 적응적이며 당신의 선택에 따라 다른 선택을 할 수 있다.

총 2ドルN$번의 차례가 진행되면 추가적인 입력 없이 게임이 종료되며 당신은 프로그램을 종료해야 한다.

만약 당신이 이미 가져간 카드를 가져가려 하거나 없는 카드를 가져가려 하는 경우 당신은 -1을 다음 줄에 입력받으며 이 입력이 주어질 경우 프로그램을 즉시 종료해야 한다.

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

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

입력

출력

제한

노트

위 예시는 입출력이 어떤 방식으로 이루어지는지 이해를 돕기 위해 의도적으로 개행 간격 등을 조절한 것으로 실제 입출력과는 다르다.