To jest zadanie interaktywne. Pamiętaj o opróżnianiu bufora wyjścia (flush) po każdym wypisaniu. Aby opróżnić wyjście, możesz użyć:

• fflush(stdout) lub cout.flush() w C/C++;
• System.out.flush() w Javie i Kotlinie;
• sys.stdout.flush() w Pythonie.

Koncepcja gry, zilustrowana przez Nano Banana Pro.

Bierzesz udział w strategicznej grze turowej znanej jako Revolver Roulette.

Gra rozpoczyna się z rewolwerem załadowanym dokładnie $6$ nabojami. Każdy nabój jest niezależnie i z równym prawdopodobieństwem ostry (live) albo ślepy (blank). Obaj gracze zawsze znają aktualną liczbę ostrych i ślepych nabojów pozostałych w bębenku, ale ich dokładna kolejność jest nieznana.

Każdy gracz zaczyna z $5$ punktami zdrowia (HP) oraz $2$ przedmiotami. Jeśli HP gracza spadnie do $0$ lub poniżej, zostaje on wyeliminowany, a drugi gracz wygrywa. Gracze wykonują akcje na zmianę.

Przebieg tury

Podczas swojej tury aktywny gracz może wykonać dowolną liczbę następujących akcji:

• Użyć dowolnego przedmiotu.
• Wykonać dowolną akcję strzału.

Tura kończy się tylko wtedy, gdy akcja strzału powoduje przejście tury na drugiego gracza lub gdy któryś z graczy zostanie wyeliminowany.

Akcje strzału

Aktywny gracz musi wybrać jedną z następujących akcji strzału:

• Fire at Opponent: Aktywny gracz wystrzeliwuje kolejny nabój w stronę przeciwnika. Jeśli nabój jest ostry, przeciwnik traci $1$ HP. Niezależnie od rodzaju naboju tura przechodzi na przeciwnika.
• Fire at Self: Aktywny gracz wystrzeliwuje kolejny nabój w siebie. Jeśli nabój jest ostry, aktywny gracz traci $1$ HP, a tura przechodzi na przeciwnika. W przeciwnym razie, jeśli nabój jest ślepy, aktywny gracz zachowuje turę i kontynuuje wykonywanie akcji.

Przedmioty

Gdy przedmiot zostaje użyty, ulega zużyciu, a aktywny gracz zachowuje turę niezależnie od rodzaju przedmiotu. Przedmioty są widoczne dla obu graczy. Gdy gracz otrzymuje nowy przedmiot (wliczając każdy z przedmiotów początkowych), jest on wybierany jednostajnie losowo spośród czterech poniższych typów:

• Dummy: Wystrzeliwuje kolejny nabój w manekina treningowego. Zużywa to nabój i nie jest traktowane jako akcja strzału.
• Magnifier: Podgląda kolejny nabój, ujawniając, czy jest on ostry, czy ślepy. Obaj gracze poznają wynik.
• Converter: Odwraca typ kolejnego naboju (ostry $\leftrightarrow$ ślepy). Obaj gracze widzą zaktualizowaną liczbę ostrych i ślepych nabojów.

• Cage: Daje jednorazowy efekt, który zapobiega zakończeniu tury przy następnej akcji strzału, która normalnie by ją zakończyła. Dokładniej:

  • Jeśli gracz później wykona Fire at Opponent (niezależnie od tego, czy nabój jest ostry, czy ślepy), efekt zadziała i tura się nie kończy.
  • Jeśli gracz później wykona Fire at Self, a nabój okaże się ostry, efekt zadziała i tura się nie kończy (gracz nadal traci $1$ HP, ale zachowuje turę).

  Efekt zużywa się natychmiast po jednokrotnym zadziałaniu. W jednej turze można użyć co najwyżej jednego przedmiotu Cage.

Przeładowanie (Reloading)

Gdy bębenek staje się pusty, natychmiast ładowanych jest $6$ nowych nabojów (każdy niezależnie ostry lub ślepy z równym prawdopodobieństwem). Obaj gracze są informowani o nowej liczbie ostrych i ślepych nabojów. Ponadto każdy gracz otrzymuje uzupełnienie przedmiotów do $2$ sztuk (gracz posiadający $k$ przedmiotów otrzymuje $(2 - k)$ nowych przedmiotów, z których każdy jest wybierany niezależnie i jednostajnie losowo spośród powyższych czterech typów).

Cel

Jesteś graczem, który wykonuje pierwszą turę, a Twoim celem jest wygranie gry poprzez wyeliminowanie przeciwnika.

Wejście

Pierwszy wiersz zawiera dwie liczby całkowite $n$ oraz $w$, oznaczające, że musisz wygrać co najmniej $w$ spośród $n$ gier, aby Twoje rozwiązanie zostało zaakceptowane. Są tylko trzy testy:

• Test przykładowy: $n = 1$ oraz $w = 0$. ($0\%$)
• Ukryty test 1: $n = 2\,000$ oraz $w = 1\,000$. ($50\%$)
• Ukryty test 2: $n = 20\,000$ oraz $w = 11\,000$. ($55\%$)

Można wykazać, że gdy obaj gracze grają optymalnie, gracz rozpoczynający wygrywa około $56.89\%$ gier.

Protokół interakcji

Początek gry

Twoje rozwiązanie działa jako gracz wykonujący pierwszą turę przeciwko interaktorowi. Na początku każdej gry interaktor wypisuje liczbę całkowitą $g$:

• Jeśli $g = 0$, wszystkie gry w bieżącym uruchomieniu zostały zakończone. Twoje rozwiązanie musi natychmiast zakończyć działanie.
• W przeciwnym razie $g$ jest indeksem bieżącej gry ($1 \le g \le n$).

Ze względów technicznych Twoje rozwiązanie jest uruchamiane dwukrotnie na każdym teście:

• Interaktor może w dowolnym momencie zdecydować o ponownym uruchomieniu Twojego rozwiązania, podając $g = 0$.

W każdym uruchomieniu w ramach testu otrzymasz te same wartości $n$ oraz $w$. W związku z tym $n$ nie zawsze jest równe liczbie gier w bieżącym uruchomieniu. Gwarantuje się, że każda gra $1, \dots, n$ zostanie rozegrana dokładnie raz łącznie w obu uruchomieniach. Poza tym Twoje rozwiązanie może bezpiecznie zignorować warunek dwukrotnego uruchomienia.

Stan gry

Następnie interaktor wypisuje wiersz stanu gry zawierający $13$ nieujemnych liczb całkowitych:

$$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\}$: status tury.
• $l, b$ ($1 \le l + b \le 6$): aktualna liczba ostrych i ślepych nabojów pozostałych w bębenku.
• $h_1$ ($0 \le h_1 \le 5$): Twoje aktualne HP.
• $d_1, m_1, c_1, k_1$ ($0 \le d_1 + m_1 + c_1 + k_1 \le 2$): liczba przedmiotów Dummy, Magnifier, Converter oraz Cage, które aktualnie posiadasz.
• $h_2$ ($0 \le h_2 \le 5$): aktualne HP Twojego przeciwnika.
• $d_2, m_2, c_2, k_2$ ($0 \le d_2 + m_2 + c_2 + k_2 \le 2$): liczba przedmiotów Dummy, Magnifier, Converter oraz Cage, które posiada Twój przeciwnik.

Przypadek $t = 0$ (Koniec gry)

Bieżąca gra dobiegła końca. Interaktor przechodzi do następnej gry (wypisując nowe $g$).

Przypadek $t = 1$ (Twoja tura)

Musisz wypisać liczbę całkowitą, aby wybrać akcję:

1. Fire at Opponent.
2. Fire at Self.
3. Użyj przedmiotu Dummy.
4. Użyj przedmiotu Magnifier.
5. Użyj przedmiotu Converter.
6. Użyj przedmiotu Cage.

Jeśli akcja jest nieprawidłowa (np. użycie przedmiotu, którego nie posiadasz, lub użycie przedmiotu Cage więcej niż raz w tej samej turze), stan gry pozostaje bez zmian, a interaktor wypisuje $0$ oraz ponownie ten sam wiersz stanu ($13$ liczb całkowitych). Mimo że nadal trwa Twoja tura, musisz wykonać inną prawidłową akcję, aby kontynuować grę.

W przeciwnym razie akcja dochodzi do skutku, a interaktor wypisuje liczbę całkowitą wyniku:

• Dla akcji $1$–$5$: Zwraca $1$, jeśli kolejny nabój przed akcją był ostry, lub $2$, jeśli był ślepy.
• Dla akcji $6$: Zwraca $1$ (żadna informacja o naboju nie zostaje ujawniona).

Następnie interaktor wypisuje zaktualizowany wiersz stanu gry.

Przypadek $t = 2$ (Tura przeciwnika)

Interaktor symuluje akcję Twojego przeciwnika i wypisuje dwa wiersze:

• Identyfikator akcji $a \in \{1, \dots, 6\}$.
• Liczbę całkowitą wyniku ($1$ lub $2$, jak opisano powyżej).

Twój przeciwnik nigdy nie wykonuje nielegalnej akcji. Natychmiast po tym interaktor wypisuje kolejny wiersz stanu gry ($13$ liczb całkowitych).

W każdej rundzie gry symulator używa generatora liczb pseudolosowych ze stałym ziarnem losowości (seed). Ponadto przeciwnik w interaktorze stosuje strategię deterministyczną. Decyzja o ponownym uruchomieniu Twojego rozwiązania jest niezależna od przebiegu interakcji. Dlatego ten sam ciąg akcji zawsze prowadzi do tego samego stanu gry.

Udostępniono narzędzie testowe, które pomoże Ci w tworzeniu i testowaniu Twojego rozwiązania.

Przykład

Przykład 1, Przebieg 1

Wejście

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

Wyjście

6


1


6


2


1








1








4


1

Przykład 1, Przebieg 2

Wejście

1 0
0

Wyjście