Algosia 和 Bajtek 處於一個非常不尋常的情況。他們每個人都擁有一個長度為 $n$ 的二進位字串。他們希望儘快交換這些字串。

問題在於，他們目前正在參加一場剪刀、石頭、布的錦標賽。這項比賽最近經歷了一場技術革命。為了避免參賽者之間進行任何形式的通訊，並專注於選手策略的隨機性，主辦單位決定將參賽者完全隔離，並在他們之間放置一個電腦系統。每位參賽者宣告他們的出拳，只有在宣告後才會揭曉該回合的結果。

剪刀、石頭、布的比賽規則如下：

• 比賽由多個回合組成。
• 在單個回合中，每位玩家選擇三個符號之一：布、石頭或剪刀。
• 接著比較這些符號。如果玩家選擇了相同的符號，則該回合以平手結束，沒有人得分。否則，擁有較強符號的人獲得 1 分（布贏石頭，石頭贏剪刀，剪刀贏布）。
• 率先比對手多出 2 分的玩家贏得比賽。
• 比賽持續進行，直到其中一名玩家贏得比賽為止。

Algosia 和 Bajtek 希望在比賽結束前互相了解對方的字串。他們也希望進行盡可能少的回合，以免耗盡觀察者和觀眾的耐心。請編寫一個程式來幫助他們。你必須為 $t$ 個獨立的測試案例解決此問題。

互動

這是一個互動式問題。你的程式將以兩個副本執行——一個用於 Algosia，另一個用於 Bajtek。每個執行檔在輸入的第一行都會收到單字 Algosia 或 Bajtek，這決定了該程式副本代表哪位參賽者。

兩種情況下的輸入格式完全相同。輸入的第一行包含單字 Algosia 或 Bajtek。第二行包含兩個數字 $n$ 和 $t$ ($1 \le n \le 5000, 1 \le t \le 5$)，分別表示 Algosia 和 Bajtek 想要互相傳送的二進位字串長度以及測試案例的數量。接著進行 $t$ 次程式間的互動。

在每個測試案例的第一行，兩個程式都會收到一個長度為 $n$ 的字串，僅由字元 0 和 1 組成。讀取各自的字串後，Algosia 和 Bajtek 開始比賽。在單個回合中，玩家首先輸出一行包含其出拳的內容，由單一字元 $c \in \{P, K, N\}$ 表示，然後從輸入中讀取一行，其中包含以相同格式表示對手出拳的字元。單個測試案例中的最大回合數為 20000。超過此限制將導致「錯誤答案」的判決。

要結束測試案例，必須輸出一行包含字元 !（驚嘆號）、一個空格，以及隨後長度為 $n$ 且僅由字元 0 和 1 組成的字串。對於 Algosia，這應該是 Bajtek 的字串，而對於 Bajtek，這應該是 Algosia 的字串。輸出結果後，程式應立即進入下一個測試案例（即讀取需要傳遞的字串），或者如果這是最後一個測試案例，則結束執行。

輸出答案後，必須清空輸出緩衝區，例如透過呼叫 cout.flush() 或 fflush(stdout)。

範例

說明

• 上述互動對應於第一個範例測試（名稱為 0a）。
• 在所有其他測試中（包括第二個範例測試 0b），均有 $t = 5, n = 5000$。
• 如果在一回合後，任何玩家比對手多出 2 分，程式將立即以「錯誤答案」判決結束。
• 兩個程式同時開始。程式執行時間測量為從 Interactor 開始到結束的實際時間。
• 領先優勢不會在測試案例之間累積。在每個案例開始時，兩位玩家都從 0 分開始（無論上一個案例以什麼結果結束）。

子任務

測試集由一組組成，最多可獲得 10 分。令 $m$ 為單個測試中所有測試案例進行的最大回合數。該測試的得分根據以下規則確定：

提交的最終得分是所有測試中的最低得分。

實作細節

在「檔案」部分中，提供了 pknsoc.cpp 互動器。它與 SIO2 上用於檢查提交的互動器相同。應使用以下指令執行它：

python3 pknrun.py [solution] < [test] > [output]

其中 pknsoc.cpp 和 oi.h 檔案必須位於同一個資料夾中。互動器接收輸入的格式在 pknsoc.cpp 檔案的註解中有描述。

公平競爭原則

禁止透過比賽過程以外的任何方式在程式之間進行通訊，例如透過一個程式延遲發送動作而另一個程式讀取時鐘。如果評審發現程式之間以不允許的方式進行通訊，提交內容可能會被刪除，在嚴重情況下，可能會決定取消整個比賽的資格。