呢題係一道交互題。

遊戲「水管工 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 分別對應波蘭文入面代表左同右嘅單詞。

你可以進行最多 $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