これはインタラクティブな問題です。

ゲーム「配管工 Mariusz」（Plumber Mariusz）は $n + 1$ 個のレベル（0 から $n$ まで番号付けされている）からなり、各レベルには $k$ 個のバージョン（0 から $k - 1$ まで番号付けされている）があります。最後を除くすべてのレベルの各バージョンの終端には、左と右の 2 本の土管があり、Mariusz はそのうちの 1 本に飛び込まなければなりません。各土管にはいくつかのコインが入っており、次のレベルのいずれかのバージョンへと繋がっています。（レベル 0 を除く）各レベルの各バージョンにはちょうど 2 本の土管が繋がっています。これらは前のレベルの全 $k$ 個のバージョンから出る $2 \cdot k$ 本の土管のうちの任意の 2 本であり得ます。

1 回のプレイは、レベル 0 のバージョンを 1 つ選び、その後左または右の土管を $n$ 回選ぶことで構成され、プレイの結果は通過した $n$ 本の土管で集めたコインの総数となります。各土管に何枚のコインが入っていたかや、各レベルのどのバージョンを訪れたかを知ることはできません。土管内のコインは常に初期値にリセットされるため、すべてのプレイは独立です。したがって、1 回のプレイは次の関数で表すことができます：

int rozgrywka(int ver, string s)、ここで $\text{ver} \in [0, k - 1]$ であり、$s$ は文字 L と P からなる長さ $n$ の文字列です。

なお、L と P はそれぞれポーランド語の左と右を表す単語に対応しています。

あなたは最大 $300\,000$ 回のテストプレイを行い、その結果を知ることができます。その後、プレイに関するクエリが最大 $10\,000$ 個与えられます。あなたの仕事はそれらの結果を求めることです。

各テストは対話が始まる前に固定されています（すなわち、ジャッジは適応的ではありません）。1 つのテストは、$n + 1$ 個の層（レベル）に配置された $(n + 1) \cdot k$ 個の頂点を持つ有向重み付きグラフと、$q$ 個のクエリ $(\text{ver}, s)$ を含みます。最後の層を除く各頂点は 2 本の出辺（左と右）を持ち、それぞれコイン数 $c \in [1, 10^8]$ と行き先のバージョン $v \in [0, k - 1]$ で記述されます。層 0 を除くすべての頂点の入次数がちょうど 2 であることを思い出してください。

バッファのフラッシュ

各行を出力した後、必ず出力バッファをフラッシュして、ジャッジが出力行を受け取れるようにしなければなりません。たとえば C++ では、感嘆符を含む行を cout << "!" << endl; または printf("!\n"); fflush(stdout); を使って出力できます。Python では print("!", flush=True) を使えます。各行の後にフラッシュせずに複数行を出力したり、ジャッジの応答を読まずに多数の行を出力したりした場合、ジャッジの安定した動作は保証されません。また、プログラムはいかなるファイルも開いてはなりません。

対話プロトコル

通信全体の流れは以下の通りです：

• 最初の行から 2 つの整数 $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$（制限は上と同じ）を含む次の行を読み込む。
  • プレイの結果（整数 1 つ）を含む行を出力する。フラッシュする。

図は最初のサンプルテスト ($n = 2; k = 4$) を示しています。2 つの最終クエリが破線で示されています：rozgrywka(0, "LL") $= 20 + 3 = 23$ および rozgrywka(1, "PL") $= 9 + 10 = 19$ です。

入出力例

以下は通信の流れの例です：

注記

添付ファイル（QOJ の「attachment」タブからダウンロードできます）には、通信は正しく行うものの結果の計算が誤っているサンプル解答 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