To jest zadanie interaktywne.

Gra „Hydraulik Mariusz” (Plumber Mariusz) składa się z $n + 1$ poziomów (ponumerowanych od 0 do $n$), z których każdy ma $k$ wersji (ponumerowanych od 0 do $k - 1$). Każda wersja każdego poziomu (oprócz ostatniego) kończy się dwiema rurami — lewą i prawą — i Mariusz musi wskoczyć do jednej z nich. Każda rura zawiera pewną liczbę monet i prowadzi do jednej z wersji następnego poziomu. Dokładnie dwie rury prowadzą do każdej wersji każdego poziomu (oprócz poziomu zerowego); mogą to być dowolne dwie spośród $2 \cdot k$ rur wychodzących ze wszystkich $k$ wersji poprzedniego poziomu.

Pojedyncza rozgrywka polega na wybraniu wersji poziomu zerowego, a następnie $n$-krotnym wybraniu lewej lub prawej rury, a wynikiem rozgrywki jest łączna liczba monet zebranych w $n$ odwiedzonych rurach. Nie dowiadujemy się, ile monet było w poszczególnych rurach ani które wersje poziomów zostały odwiedzone. Monety w rurach zawsze resetują się do swoich początkowych wartości, więc wszystkie rozgrywki są niezależne. Rozgrywkę można zatem przedstawić za pomocą funkcji:

int rozgrywka(int ver, string s), gdzie $\text{ver} \in [0, k - 1]$ oraz $s$ jest napisem złożonym z $n$ liter L i P.

Zauważ, że L i P odpowiadają polskim słowom oznaczającym odpowiednio lewo i prawo.

Możesz wykonać do $300\,000$ testowych rozgrywek i poznać ich wyniki. Następnie otrzymasz do $10\,000$ zapytań o rozgrywki. Twoim zadaniem jest wyznaczenie ich wyników.

Każdy test jest ustalony przed rozpoczęciem interakcji (tzn. interaktor nie jest adaptacyjny). Test zawiera skierowany graf ważony o $(n + 1) \cdot k$ wierzchołkach ułożonych w $n + 1$ warstwach (poziomach) oraz $q$ zapytań $(\text{ver}, s)$. Każdy wierzchołek (oprócz tych w ostatniej warstwie) ma dwie krawędzie wychodzące (lewą i prawą), z których każda jest opisana liczbą monet $c \in [1, 10^8]$ oraz wersją $v \in [0, k - 1]$, do której prowadzi. Przypomnijmy, że każdy wierzchołek oprócz tych w warstwie zerowej ma stopień wejściowy równy dokładnie 2.

Opróżnianie bufora (Buffer flushing)

Po wypisaniu każdego wiersza musisz opróżnić bufor wyjścia (flush), aby interaktor otrzymał wypisany wiersz. Na przykład w C++ możesz wypisać wiersz zawierający wykrzyknik za pomocą cout << "!" << endl; lub printf("!\n"); fflush(stdout);. W Pythonie możesz użyć print("!", flush=True). Nie gwarantujemy stabilnego działania interaktora, jeśli wypiszesz wiele wierszy bez opróżnienia bufora po każdym z nich lub jeśli wypiszesz wiele wierszy bez odczytania odpowiedzi interaktora. Twój program nie może otwierać żadnych plików.

Protokół interakcji

Pełny przebieg komunikacji opisano poniżej:

• Wczytaj pierwszy wiersz zawierający dwie liczby całkowite $n$ oraz $k$ ($1 \le n, k \le 20$) — jest $n + 1$ poziomów, każdy w $k$ wersjach.
• Co najwyżej $300\,000$ razy wykonaj testową rozgrywkę:
  • Wypisz wiersz postaci ? ver s (bez cudzysłowów), gdzie $\text{ver} \in [0, k - 1]$ oraz $s$ jest napisem złożonym z $n$ liter L i P. Opróżnij bufor.
  • Wczytaj kolejny wiersz zawierający wynik rozgrywki — liczbę całkowitą $x$ ($n \le x \le n \cdot 10^8 \le 2 \cdot 10^9$).
• Wypisz wiersz zawierający pojedynczy znak ! (wykrzyknik). Opróżnij bufor.
• Wczytaj kolejny wiersz zawierający liczbę całkowitą $q$ ($1 \le q \le 10\,000$) — liczbę zapytań.
• Dla każdego z $q$ zapytań:
  • Wczytaj kolejny wiersz zawierający liczbę całkowitą $\text{ver}$ oraz napis $s$ (z takimi samymi ograniczeniami jak wyżej).
  • Wypisz wiersz zawierający wynik rozgrywki (liczbę całkowitą). Opróżnij bufor.

Ilustracja przedstawia pierwszy test przykładowy ($n = 2; k = 4$). Dwa końcowe zapytania zaznaczono linią przerywaną: rozgrywka(0, "LL") $= 20 + 3 = 23$ oraz rozgrywka(1, "PL") $= 9 + 10 = 19$.

Przykład

Oto przykładowy przebieg komunikacji:

Uwaga

W załączniku (można go pobrać w zakładce „attachment” na QOJ) znajdziesz przykładowe (błędne) rozwiązania G.cpp i G.py, które przeprowadzają komunikację poprawnie, ale błędnie obliczają wyniki. Katalog zawiera także: przykładowy sprawdzacz Gsoc.cpp oraz testy przykładowe (G0a.in, G0b.in, G0c.in oraz duży losowy test G0d.in z $n = k = 20$). Format plików testowych opisano w komentarzu na początku pliku Gsoc.cpp.

Przykładowy sprawdzacz Gsoc.cpp różni się od tego używanego na QOJ. Może on nie weryfikować poprawności wejścia ani argumentów funkcji rozgrywki.

Możesz uruchomić swoje rozwiązanie za pomocą skryptu run.sh. Polecenie przyjmuje skompilowany program oraz nazwę pliku testowego. Na przykład, aby uruchomić programy przykładowe na teście przykładowym G0a.in:

• C++: g++ G.cpp -o G.e && ./run.sh "./G.e" G0a.in
• Python: ./run.sh "python3 G.py" G0a.in