Algosia i Bajtek znaleźli się w bardzo nietypowej sytuacji. Każde z nich posiada swój własny ciąg binarny długości $n$. Chcieliby się tymi ciągami jak najszybciej wymienić.

Sprawę utrudnia fakt, że aktualnie przebywają oni na mistrzostwach gry w papier, kamień, nożyce. Konkurs ten ostatnio przeszedł technologiczną rewolucję. Aby uniknąć jakichkolwiek prób komunikacji między uczestnikami i w pełni skupić się na losowości strategii zawodników, organizatorzy postanowili całkowicie odizolować od siebie uczestników i postawić między nimi system komputerowy. Każdy z uczestników deklaruje swój ruch i dopiero po tym odsłaniane są wyniki rundy.

Zasady meczu w papier, kamień, nożyce są następujące:

• Mecz składa się z rund.
• Podczas pojedynczej rundy każdy z graczy wybiera jeden z trzech symboli: papier, kamień lub nożyce.
• Następnie symbole te są porównywane. Jeśli gracze wybrali ten sam symbol, to runda kończy się remisem i nikt nie zdobywa punktu. W przeciwnym przypadku osoba z silniejszym symbolem zdobywa 1 punkt (papier wygrywa z kamieniem, kamień wygrywa z nożycami, a nożyce wygrywają z papierem).
• Gracz, który jako pierwszy będzie miał o 2 punkty więcej niż przeciwnik, wygrywa mecz.
• Rundy trwają, dopóki któryś z graczy nie wygra meczu.

Algosi i Bajtkowi zależy na tym, aby nawzajem poznać swoje słowa jeszcze przed końcem meczu. Chcieliby też grać jak najmniej rund, żeby nie nadwyrężać cierpliwości obserwatorów i kibiców. Napisz program, który im w tym pomoże. Musisz rozwiązać ten problem dla $t$ niezależnych przypadków testowych.

Interakcja

To jest zadanie interaktywne. Twój program zostanie uruchomiony w dwóch kopiach – jednej dla Algosi, a drugiej dla Bajtka. Każde z uruchomień w pierwszym wierszu wejścia otrzyma słowo Algosia lub Bajtek, które określa za działanie której z osób odpowiada ta kopia programu.

Format wejścia w obu przypadkach wygląda identycznie. Pierwszy wiersz wejścia zawiera słowo Algosia lub Bajtek. Drugi wiersz zawiera dwie liczby $n$ i $t$ ($1 \le n \le 5000, 1 \le t \le 5$), określające kolejno długość ciągów binarnych, jakie chcą między sobą przesłać Algosia i Bajtek oraz liczbę przypadków testowych. Następnie $t$ razy odbywa się interakcja między programami.

W pierwszym wierszu każdego przypadku testowego obydwa programy otrzymają napis długości $n$, składający się tylko ze znaków 0 i 1. Po wczytaniu swoich napisów Algosia i Bajtek zaczynają rozgrywkę. Podczas pojedynczej rundy gracz najpierw wypisuje wiersz zawierający jego ruch, określany jednym znakiem $c \in \{P, K, N\}$, a następnie wczytuje z wejścia wiersz zawierający znak określający ruch drugiego gracza w tym samym formacie. Maksymalna liczba odbytych rund w pojedynczym przypadku testowym wynosi 20000. Przekroczenie tego limitu będzie skutkować werdyktem „błędna odpowiedź”.

Aby zakończyć przypadek testowy, należy wypisać wiersz zawierający znak ! (wykrzyknik), odstęp oraz następujący po nim napis długości $n$ składający się tylko ze znaków 0 i 1. Dla Algosi powinien być to napis Bajtka, zaś dla Bajtka napis Algosi. Po wypisaniu wyniku program powinien od razu przejść do kolejnego przypadku testowego (czyli wczytać wiersz zawierający napis, który należy przekazać) lub zakończyć działanie, jeśli był to ostatni przypadek testowy.

Po wypisaniu odpowiedzi należy opróżnić bufor wyjścia, na przykład poprzez wywołanie polecenia cout.flush() lub fflush(stdout).

Przykład

Wejście 1

Algosia
5 2
10010
P
K
P
P
! 00001
00010
P
K
! 10001

Wyjście 1

K
P
P
P
! 10010
K
P
! 00010

Uwagi

• Opisana powyżej interakcja odpowiada pierwszemu testowi przykładowemu (o nazwie 0a).
• We wszystkich pozostałych testach (również w drugim teście przykładowym o nazwie 0b) zachodzi $t = 5, n = 5000$.
• Jeśli po rundzie któryś z graczy ma o 2 punkty więcej niż przeciwnik, program od razu kończy się z werdyktem „błędna odpowiedź”.
• Obydwa programy rozpoczynają się w tym samym czasie. Czas działania programu mierzony jest jako czas rzeczywisty od rozpoczęcia do zakończenia interaktora.
• Przewagi nie przenoszą się między przypadkami testowymi. Na początku każdego przypadku obaj gracze zaczynają z 0 punktami (niezależnie od tego, z jakim wynikiem skończył się poprzedni przypadek).

Ocenianie

Zestaw testów składa się z jednej grupy, za którą można dostać maksymalnie 10 punktów. Niech $m$ oznacza maksymalną liczbę odbytych rund po wszystkich przypadkach testowych pojedynczego testu. Wynik za dany test określany jest według następujących zasad:

Końcowy wynik zgłoszenia to minimalny wynik po wszystkich testach.

Testowanie lokalne

W sekcji Pliki dostępny jest interaktor pknsoc.cpp. Jest on identyczny jak interaktor używany do sprawdzania zgłoszeń na SIO2. Należy go uruchamiać komendą:

python3 pknrun.py [rozwiazanie] < [test] > [wyjscie]

przy czym pliki pknsoc.cpp oraz oi.h muszą znajdować się w tym samym folderze. Format, w którym interaktor przyjmuje wejście, jest opisany w komentarzu w pliku pknsoc.cpp.

Zasady fair play

Komunikowanie się pomiędzy programami w inny sposób niż za pomocą przebiegu rozgrywki, np. poprzez wysłanie ruchu przez jeden program z opóźnieniem i odczytanie zegara przez drugi jest zabronione. W przypadku stwierdzenia przez Jury próby komunikowania się między programami w niedozwolony sposób zgłoszenie może zostać usunięte, a w rażących przypadkach może zostać podjęta decyzja o dyskwalifikacji z całego konkursu.