28697번 - 오락 고! 인터랙티브

문제

이 문제는 인터랙티브 문제이다. 아래 노트에 나와 있는 방식으로 입출력을 진행해야 한다.

<계란을 떨어뜨리면?>에서 재우가 달걀을 떨어뜨리던 동안, 주영이는 지하 1ドル$층의 오락실에서 <오락 고?>의 현제와 같이 리듬 게임을 하고 있었다. 그런데 천장에 자꾸 무언가 부딪히는 소리가 나는 바람에 현제는 리듬 게임에 집중할 수 없었다! 주영이와 현제가 1ドル$층에 올라가자 열심히 달걀을 떨어뜨리는 재우와 재우가 마트에서 잔뜩 사 온 달걀을 발견할 수 있었다. 리듬 게임을 방해받아 화가 난 현제는 재우가 사 온 달걀을 모두 뺏어 오락실에 가져다 놓았다.

리듬 게임을 방해받아 더 이상 리듬 게임을 할 기분이 아닌 현제에게, 주영이는 달걀로 할 수 있는 게임을 하나 제안했다. 게임은 3ドル$단계로 나누어져 진행된다.

1ドル$단계에서는 주영이가 3ドル$ 이상의 양의 정수 $n$을 부르고, 달걀을 담을 $n$개의 바구니를 원형으로 놓는다. 각 바구니에는 1ドル$번부터 $n$번까지 시계방향 순서로 번호가 붙어 있다.

2ドル$단계에서는 $n$개의 달걀을 배치한다. 재우가 사 온 달걀에는 일련번호가 하나씩 찍혀 있으며, 그중 게임에서는 일련번호가 1ドル$번, 2ドル$번, ..., $n$번인 달걀 각각 하나씩만을 사용한다. 화가 난 현제를 배려해 주영이는 현제에게 먼저 달걀을 놓을지, 나중에 달걀을 놓을지 선택하게 해 주었다. 만약 현제가 먼저 달걀을 놓겠다고 하면, 아래와 같이 진행된다.

• 먼저 현제는 1ドル$번 달걀을 1ドル$번 바구니에 놓는다.
• 다음으로 주영이는 2ドル$번 달걀을 비어있는 바구니 중 원하는 바구니에 놓는다.
• 다음으로 현제는 3ドル$번 달걀을 비어있는 바구니 중 원하는 바구니에 놓는다.

이런 식으로 현제와 주영이가 번갈아 가며 비어있는 바구니 중 원하는 곳에 달걀을 놓으며(1ドル$번 달걀은 예외로, 1ドル$번 달걀은 반드시 1ドル$번 바구니에 놓는다), $n$개의 달걀을 다 배치하면 멈춘다.

단, 1ドル$번 달걀이 놓인 후에는 둘 다 자신의 차례 때 달걀을 놓는 대신 “오락 고!”라고 외칠 수 있으며, 그 사람은 탐색자가 된다.

탐색자가 아닌 사람은 조정자가 되며, 현재 상태에서 남은 달걀을 전부 자신이 원하는 대로 바구니에 놓는다. 조정자가 남은 달걀을 원하는 대로 놓을 때도 비어있는 바구니에만 달걀을 놓을 수 있으며, 하나의 바구니에 두 개 이상의 달걀이 들어가게 놓을 수는 없다.

만약 둘 다 “오락 고!”라고 외치치 않은 채 누군가 $n$번 달걀을 놓았다면 $n$번 달걀을 놓은 사람이 조정자가 되며, 남은 사람이 탐색자가 된다.

3ドル$단계에서는 탐색자가 조건이 맞는 달걀이 있는지 찾는다.

탐색자는 다음 시행을 $n$번 반복한다.

• $i$번째 시행에서, 탐색자는 $i$번 달걀을 찾아가 그 달걀에 좌우로 인접해 있는 달걀 하나씩을 집어, 두 달걀의 위치를 바꿔서 놓는다.

탐색자가 시행하는 도중 3ドル$개의 달걀, 즉 $i$번 달걀과 좌우로 인접해 있는 두 달걀의 일련번호가 오름차순, 또는 내림차순인 경우가 있다면(예를 들어 5ドル$번째 시행에서 5ドル$번 달걀 왼쪽에 2ドル$번 달걀, 오른쪽에 7ドル$번 달걀이 있다면) 즉시 탐색자의 승리로 게임을 종료한다.

탐색자가 $n$번의 시행을 모두 마쳤음에도 오름차순이나 내림차순인 달걀을 찾지 못했다면, 조정자의 승리로 게임을 종료한다.

현제가 게임에서 지면 오늘의 일이 안 좋은 기억으로 남아 앞으로 평생 리듬 게임을 하지 않을지도 모른다! 현제가 앞으로도 리듬 게임을 할 수 있도록 현제를 도와 게임에서 승리해 보자.

입력

첫 번째 줄에 1ドル$단계에서 주영이가 부른 양의 정수 $n$ (3ドル \le n \leq 10,000円$)이 주어진다.

출력

첫 줄에 2단계에서 먼저 달걀을 놓을지, 나중에 달걀을 놓을지 선택한다. 먼저 달걀을 놓는다면 first를, 나중에 달걀을 놓는다면 late를 출력한다.

late를 출력했다면 주영이는 즉시 1ドル$번 달걀을 1ドル$번 바구니에 놓는다. 이는 입력으로 주어지지 않는다.

현재 상태에서 “오락 고!”라고 외치려면 다음 줄에 orakGo를 출력한다. 그렇지 않다면, 다음 줄에 다음 달걀을 놓을 바구니의 번호를 출력한다.

바구니의 번호를 출력했다면, 주영이는 현제의 행동을 보고 입력을 결정한다. 이 입력은 2ドル$ 이상 $n$ 이하의 정수이거나 orakGo이다.

입력으로 정수가 주어진다면, 이 입력은 주영이가 다음 달걀을 놓은 바구니의 번호를 의미한다. 이후 현재 상태에서 “오락 고!”라고 외칠지 다음 달걀을 놓을지 선택해 위와 같은 방법으로 출력한다.

orakGo를 출력하거나, orakGo를 입력으로 받거나, $n$번 달걀을 놓을 바구니의 번호를 출력했거나, $n$번 달걀을 놓을 바구니의 번호가 입력으로 주어진다면 출력을 종료해야 한다.

출력을 종료한 후의 상태로 3ドル$단계를 진행했을 때, 현제가 진다면 틀렸습니다를 받는다.

만약 1ドル$번 달걀을 1ドル$번 바구니에 놓지 않거나 이미 달걀이 들어 있는 바구니에 달걀을 놓는다면, 게임의 규칙을 어겼으므로 틀렸습니다를 받는다. 주영이는 게임의 규칙을 아주 잘 지키기 때문에 입력으로 이미 달걀이 들어 있는 바구니의 번호가 주어질 일은 없음이 보장된다.

제한

노트

3ドル$단계에서 탐색자가 이긴다는 것은, 조정자가 남은 달걀을 어떻게 배치해도 탐색자는 항상 오름차순이나 내림차순으로 놓인 달걀을 찾을 수 있다는 것이다.

3ドル$단계에서 탐색자가 진다는 것은, 탐색자가 오름차순이나 내림차순으로 놓인 달걀을 찾을 수 없게 하는 배치가 존재한다는 것이다.

본 문제의 지문은 픽션으로, 사실 현제는 게임에서 지더라도 리듬 게임을 할 것이다.

인터랙티브 문제의 경우 출력을 하고, 언어에 따라 아래와 같은 명령어를 바로 다음에 적어 출력 버퍼를 flush 해줘야 한다.

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