這是一道互動題。

「水管工 Mariusz」（Plumber Mariusz）遊戲包含 $n + 1$ 個層級（編號從 0 到 $n$），每一層都有 $k$ 個版本（編號從 0 到 $k - 1$）。除最後一層外，每一層的每個版本末端都有兩條水管——左水管和右水管——Mariusz 必須跳入其中一條。每條水管包含一定數量的硬幣，並通往下一層級的某個版本。除第 0 層外，每一層的每個版本都恰好有兩條水管通往它；這兩條水管可以是上一層所有 $k$ 個版本引出的 $2 \cdot k$ 條水管中的任意兩條。

單次遊玩過程包括：選擇第 0 層的一個版本，然後選擇左水管或右水管 $n$ 次，而遊玩的結果是在經過的 $n$ 條水管中收集到的硬幣總數。我們無法得知每條水管中有多少硬幣，也無法得知具體經過了哪些層級版本。水管中的硬幣總是會重置為初始值，因此所有遊玩過程都是獨立的。因此，一次遊玩過程可以用以下函式表示：

int rozgrywka(int ver, string s)，其中 $\text{ver} \in [0, k - 1]$，$s$ 是一個由 $n$ 個字母 L 和 P 組成的字串。

注意，L 和 P 分別對應波蘭語中的左（left）和右（right）。

你可以執行最多 $300\,000$ 次測試遊玩並獲知其結果。之後，你將收到最多 $10\,000$ 個關於遊玩過程的查詢。你的任務是確定這些查詢的結果。

每個測試點在互動開始前就已經固定（即互動器不是自適應的）。一個測試點包含一個有向加權圖，該圖有 $(n + 1) \cdot k$ 個頂點，排列在 $n + 1$ 個層級中，以及 $q$ 個查詢 $(\text{ver}, s)$。每個頂點（最後一層除外）都有兩條出邊（左和右），每條邊由硬幣數量 $c \in [1, 10^8]$ 和它通往的版本 $v \in [0, k - 1]$ 描述。請記住，除第 0 層外，每個頂點的入度恰好為 2。

緩衝區刷新

在輸出每一行後，你必須刷新輸出緩衝區，以便互動器能夠接收到該行輸出。例如，在 C++ 中，你可以使用 cout << "!" << endl; 或者 printf("!\n"); fflush(stdout); 輸出一行感嘆號。在 Python 中，你可以使用 print("!", flush=True)。如果你在沒有刷新緩衝區的情況下輸出多行，或者在沒有讀取互動器回應的情況下輸出過多行，我們不保證互動器的行為穩定。你的程式不得開啟任何檔案。

互動協議

完整的通信流程描述如下：

• 讀取第一行，包含兩個整數 $n$ 和 $k$（$1 \le n, k \le 20$）——表示共有 $n + 1$ 個層級，每個層級有 $k$ 個版本。
• 執行最多 $300\,000$ 次測試遊玩：
  • 輸出一行格式為 ? ver s 的內容（不含引號），其中 $\text{ver} \in [0, k - 1]$，$s$ 是一個由 $n$ 個字母 L 和 P 組成的字串。刷新緩衝區。
  • 讀取下一行，包含遊玩結果——一個整數 $x$（$n \le x \le n \cdot 10^8 \le 2 \cdot 10^9$）。
• 輸出一行包含單個字元 !（感嘆號）。刷新緩衝區。
• 讀取下一行，包含一個整數 $q$（$1 \le q \le 10\,000$）——查詢的數量。
• 對於 $q$ 個查詢中的每一個：
  • 讀取下一行，包含一個整數 $\text{ver}$ 和一個字串 $s$（限制同上）。
  • 輸出一行，包含遊玩結果（一個整數）。刷新緩衝區。

插圖展示了第一個範例測試（$n = 2; k = 4$）。兩個最終查詢用虛線標記：rozgrywka(0, "LL") $= 20 + 3 = 23$ 和 rozgrywka(1, "PL") $= 9 + 10 = 19$。

範例

以下是一個通信流程範例：

說明

在附件中（你可以在 QOJ 的「附件」分頁下載），你會找到範例（不正確的）解答 G.cpp 和 G.py，它們能正確執行通信，但計算結果不正確。該目錄還包括：一個範例檢查器 Gsoc.cpp 和範例測試（G0a.in、G0b.in、G0c.in 以及一個 $n = k = 20$ 的大型隨機測試 G0d.in）。測試檔案的格式在 Gsoc.cpp 開頭的註解中有描述。

範例檢查器 Gsoc.cpp 與 QOJ 上使用的檢查器不同。它可能不會驗證輸入或遊玩函式的參數。

你可以使用腳本 run.sh 執行你的解答。該命令接收編譯後的程式和測試檔案名稱。例如，要在範例測試 G0a.in 上執行範例程式：

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