이 문제는 인터랙티브 문제입니다. 매 출력 후 출력 버퍼를 비우는(flush) 것을 잊지 마세요. 출력 버퍼를 비우기 위해 다음을 사용할 수 있습니다:

• C/C++에서는 fflush(stdout) 또는 cout.flush();
• Java와 Kotlin에서는 System.out.flush();
• Python에서는 sys.stdout.flush().

Nano Banana Pro가 그린 게임 컨셉 일러스트.

여러분은 리볼버 룰렛(Revolver Roulette)이라 불리는 전략 턴제 게임에 참가하고 있습니다.

게임은 정확히 $6$발의 총알이 장전된 리볼버로 시작합니다. 각 총알은 독립적으로 동일한 확률로 실탄(live) 또는 공포탄(blank)입니다. 두 플레이어는 실린더에 남아 있는 실탄과 공포탄의 현재 개수를 항상 알고 있지만, 정확한 순서는 알지 못합니다.

각 플레이어는 체력(HP) $5$와 아이템 $2$개를 가지고 시작합니다. 플레이어의 HP가 $0$ 이하로 떨어지면 탈락하며, 상대 플레이어가 승리합니다. 플레이어들은 번갈아 가며 턴을 진행하고 행동을 수행합니다.

턴 진행 절차

자신의 턴 동안 현재 턴인 플레이어는 다음 행동을 원하는 횟수만큼 수행할 수 있습니다:

• 아무 아이템이나 사용합니다.
• 아무 사격 행동이나 수행합니다.

사격 행동으로 인해 턴이 상대 플레이어에게 넘어가거나, 어느 한 플레이어가 탈락할 때만 턴이 종료됩니다.

사격 행동

현재 턴인 플레이어는 다음 사격 행동 중 하나를 선택해야 합니다:

• Fire at Opponent: 현재 플레이어가 다음 총알을 상대 플레이어에게 발사합니다. 실탄이면 상대 플레이어는 $1$ HP를 잃습니다. 총알 종류에 관계없이 턴은 상대 플레이어에게 넘어갑니다.
• Fire at Self: 현재 플레이어가 다음 총알을 자신에게 발사합니다. 실탄이면 현재 플레이어는 $1$ HP를 잃고 턴이 상대 플레이어에게 넘어갑니다. 반대로 공포탄이면 현재 플레이어는 턴을 유지하며 계속해서 행동을 수행합니다.

아이템

아이템을 사용하면 해당 아이템은 소모되며, 아이템 종류에 관계없이 현재 플레이어는 턴을 유지합니다. 아이템은 두 플레이어 모두에게 보입니다. 플레이어가 새로운 아이템(초기 아이템 각각을 포함)을 얻을 때는 다음 네 가지 종류 중에서 균등하게 무작위로 선택됩니다:

• Dummy: 훈련용 더미에 다음 총알을 발사합니다. 총알이 소모되며 사격 행동으로 간주되지 않습니다.
• Magnifier: 다음 총알을 엿보아 실탄인지 공포탄인지 밝혀냅니다. 두 플레이어 모두 결과를 알게 됩니다.
• Converter: 다음 총알의 종류를 뒤집습니다(실탄 $\leftrightarrow$ 공포탄). 두 플레이어 모두 갱신된 실탄과 공포탄의 개수를 확인합니다.

• Cage: 원래대로라면 턴이 끝나게 될 다음 사격 행동에서 턴이 끝나지 않게 막아주는 일회성 효과를 얻습니다. 구체적으로는 다음과 같습니다:

  • 플레이어가 이후 Fire at Opponent를 수행하면(총알이 실탄이든 공포탄이든 관계없이), 효과가 적용되어 턴이 끝나지 않습니다.
  • 플레이어가 이후 Fire at Self를 수행하고 총알이 실탄이면, 효과가 적용되어 턴이 끝나지 않습니다(플레이어는 여전히 $1$ HP를 잃지만 턴을 유지합니다).

  이 효과는 한 번 적용된 직후 소모됩니다. 한 턴에는 최대 하나의 Cage 아이템만 사용할 수 있습니다.

재장전 (Reloading)

실린더가 비면 즉시 새로운 총알 $6$발이 장전됩니다(각각 독립적으로 동일한 확률로 실탄 또는 공포탄). 두 플레이어에게 새로운 실탄과 공포탄의 개수가 공지됩니다. 또한 각 플레이어는 아이템이 최대 $2$개가 되도록 보충받습니다(아이템을 $k$개 가진 플레이어는 $(2 - k)$개의 새 아이템을 받으며, 각각 위 네 가지 종류 중에서 독립적으로 균등하게 무작위로 선택됩니다).

목표

여러분은 첫 번째 턴을 가지는 선공 플레이어이며, 목표는 상대를 탈락시켜 게임에서 승리하는 것입니다.

입력

첫째 줄에 두 정수 $n$과 $w$가 주어지며, 이는 정답 판정을 받기 위해 $n$번의 게임 중 적어도 $w$번 승리해야 함을 나타냅니다. 테스트는 단 세 개뿐입니다:

• 예제 테스트: $n = 1$ 및 $w = 0$. ($0\%$)
• 비밀 테스트 1: $n = 2\,000$ 및 $w = 1\,000$. ($50\%$)
• 비밀 테스트 2: $n = 20\,000$ 및 $w = 11\,000$. ($55\%$)

두 플레이어가 모두 최적으로 플레이할 때 선공 플레이어가 약 $56.89\%$의 게임을 승리한다는 것을 보일 수 있습니다.

인터랙션 프로토콜

게임 시작

여러분의 솔루션은 인터랙터를 상대로 첫 턴을 잡는 플레이어 역할을 합니다. 각 게임이 시작될 때 인터랙터는 정수 $g$를 출력합니다:

• 만약 $g = 0$이면 현재 실행(run)의 모든 게임이 완료된 것입니다. 솔루션은 즉시 종료되어야 합니다.
• 그렇지 않으면 $g$는 현재 게임 번호($1 \le g \le n$)입니다.

기술적인 문제로 인해 여러분의 솔루션은 각 테스트에서 두 번 실행됩니다:

• 인터랙터는 언제든지 $g = 0$을 주어 솔루션을 재시작할지 결정할 수 있습니다.

한 테스트 내의 각 실행에서는 동일한 $n$과 $w$를 받게 됩니다. 따라서 $n$이 현재 실행에서의 게임 수와 항상 같지는 않습니다. 두 번의 실행에 걸쳐 각 게임 $1, \dots, n$이 정확히 한 번씩 진행됨이 보장됩니다. 이 점 외에는 두 번 실행된다는 조건을 무시해도 무방합니다.

게임 상태

그다음 인터랙터는 $13$개의 음이 아닌 정수를 포함하는 게임 상태 줄을 출력합니다:

$$t \quad l \quad b \quad h_1 \quad d_1 \quad m_1 \quad c_1 \quad k_1 \quad h_2 \quad d_2 \quad m_2 \quad c_2 \quad k_2$$

• $t \in \{0, 1, 2\}$: 턴 상태.
• $l, b$ ($1 \le l + b \le 6$): 현재 실린더에 남아 있는 실탄과 공포탄의 개수.
• $h_1$ ($0 \le h_1 \le 5$): 여러분의 현재 HP.
• $d_1, m_1, c_1, k_1$ ($0 \le d_1 + m_1 + c_1 + k_1 \le 2$): 여러분이 현재 보유한 Dummy, Magnifier, Converter, Cage 아이템의 개수.
• $h_2$ ($0 \le h_2 \le 5$): 상대의 현재 HP.
• $d_2, m_2, c_2, k_2$ ($0 \le d_2 + m_2 + c_2 + k_2 \le 2$): 상대가 보유한 Dummy, Magnifier, Converter, Cage 아이템의 개수.

경우 $t = 0$ (게임 종료)

현재 게임이 종료되었습니다. 인터랙터는 다음 게임으로 넘어갑니다(새로운 $g$ 출력).

경우 $t = 1$ (여러분의 턴)

행동을 선택하기 위해 정수 하나를 출력해야 합니다:

1. Fire at Opponent.
2. Fire at Self.
3. Dummy 아이템 사용.
4. Magnifier 아이템 사용.
5. Converter 아이템 사용.
6. Cage 아이템 사용.

행동이 유효하지 않으면(예: 보유하지 않은 아이템을 사용하거나, 같은 턴에 Cage 아이템을 두 번 이상 사용하는 경우), 게임 상태는 변하지 않으며 인터랙터는 $0$과 동일한 상태 줄($13$개의 정수)을 다시 출력합니다. 여전히 여러분의 턴이지만, 게임을 진행하려면 다른 유효한 행동을 해야 합니다.

유효한 행동이라면 행동이 적용되고 인터랙터는 결과 정수를 출력합니다:

• 행동 $1$–$5$: 행동 직전의 다음 총알이 실탄이면 $1$, 공포탄이면 $2$를 반환합니다.
• 행동 $6$: $1$을 반환합니다(총알 정보는 공개되지 않음).

그 후 인터랙터는 갱신된 게임 상태 줄을 출력합니다.

경우 $t = 2$ (상대의 턴)

인터랙터는 상대의 행동을 시뮬레이션하고 두 줄을 출력합니다:

• 행동 ID $a \in \{1, \dots, 6\}$.
• 결과 정수(위에서 설명한 $1$ 또는 $2$).

상대는 절대 규칙에 어긋나는 행동을 하지 않습니다. 직후에 인터랙터는 다음 게임 상태 줄($13$개의 정수)을 출력합니다.

게임의 각 라운드에서 게임 시뮬레이터는 고정된 랜덤 시드를 가진 의사 난수 생성기를 사용합니다. 또한 인터랙터의 상대는 결정론적 전략을 사용합니다. 솔루션을 재시작할지 여부는 인터랙션 과정과 독립적입니다. 따라서 동일한 행동 순서열은 항상 동일한 게임 상태로 이어집니다.

솔루션을 개발하고 테스트하는 데 도움이 되도록 테스팅 도구가 제공됩니다.

예제

예제 1, 실행 1

입력

1 0
1
1 3 3 5 0 0 0 2 5 1 0 1 0

1
1 3 3 5 0 0 0 1 5 1 0 1 0

1
1 2 3 5 0 0 0 1 4 1 0 1 0

0
1 2 3 5 0 0 0 1 4 1 0 1 0

2
1 2 2 5 0 0 0 1 4 1 0 1 0

1
2 1 2 5 0 0 0 1 3 1 0 1 0
5
2
2 2 1 5 0 0 0 1 3 1 0 0 0
1
1
1 1 1 4 0 0 0 1 3 1 0 0 0

1
2 0 1 4 0 0 0 1 2 1 0 0 0
3
2
2 2 4 4 0 1 0 1 2 0 1 0 1
2
1
1 1 4 4 0 1 0 1 1 0 1 0 1

1
1 1 4 4 0 0 0 1 1 0 1 0 1

1
0 0 4 4 0 0 0 1 0 0 1 0 1
0

출력

6


1


6


2


1








1








4


1

예제 1, 실행 2

입력

1 0
0

출력