問題文

これはインタラクティブな要素がある問題です。

0 以上 10^{18} 以下の整数 X が与えられます。

以下の説明を読み、X を符号化する encode プログラムと、復号する decode プログラムを実装してください。

encode プログラムによって符号化された X の情報だけをもとに、 decode プログラムによって X を復号できれば正答となります。

encode プログラム

encode プログラムでは、与えられた整数 X を 150 行 150 列のグリッド H に符号化する。

まず、整数 X および 150 行 150 列の初期グリッド G の情報が入力される。

G の各マスは空マス . か壁マス # のいずれかであり、後述する「初期グリッド生成」によって生成される。

あなたは G の空マス . それぞれについて以下のいずれかを行うことでグリッド H を作り、出力しなければならない。

• 壁マス # に置き換える。
• Sマス S に置き換える。
• 空マス . のままにする。

ただしグリッド H において、Sマスはグリッド上に必ず 1 マスだけ存在するようにしなければならない。

decode プログラム

decode プログラムでは、グリッド H の情報から整数 X を復号する。

ただし、 H の情報は直接入力されない。その代わりに、グリッド H 上にいるロボットを操作することができる。

グリッドの i 行 j 列目のマスを、マス (i, j) と呼ぶことにする。

はじめ、ロボットは H の Sマスにいる。あなたは以下の「操作」を何回か行うことができる。

• 上下左右の 4 方向のうちの 1 つをロボットに伝える。
• ロボットは、現在いるマスからその向きにある隣り合ったマスに移動しようとする。
  • つまり、ロボットがマス (i, j) にいるとすると、
    • ロボットに伝えた方向が上であるとき、ロボットはマス (i-1, j) に、
    • ロボットに伝えた方向が下であるとき、ロボットはマス (i+1, j) に、
    • ロボットに伝えた方向が左であるとき、ロボットはマス (i, j-1) に、
    • ロボットに伝えた方向が右であるとき、ロボットはマス (i, j+1) に移動しようとする。
• そのマスが壁マス # でなく、グリッドの外でもなければ移動し、壁マス # かグリッドの外であれば移動しない。
• その後、ロボットが Sマスにいるかどうかがあなたに伝えられる。
• ロボットの移動が成功したかどうかはあなたには伝えられない。

何回かの「操作」の後、あなたは復号した整数 X を出力しなければならない。

初期グリッド生成

初期グリッド G には 3800 個の壁マス # がランダムに配置されている。

壁マスの周囲 8 マスには、他の壁マスが存在しないことが保証されている。

マス (i, j) の周囲 8 マスとは、マス (i-1, j-1), (i-1, j), (i-1, j+1), (i, j-1), (i, j+1), (i+1, j-1), (i+1, j), (i+1, j+1) のことである。

具体的には、初期グリッドは以下のように生成される。

• はじめ、グリッドのすべてのマスは空マス . である。
• 3800 個の壁マスが置かれるまで以下を繰り返す。
  • 周囲 8 マスに壁マスがないような空マスを候補として列挙し、その中からランダムに 1 つのマスを選び、それを壁マスに置き換える。
  • グリッドの縁にある空マスについても同様に、その周りに壁マスがなければ候補に含まれる。
  • もしそのようなマスがなく、3800 個の壁マスを置くことができないことがわかったら、そのグリッドを捨てて、新しくグリッドを生成しなおす。
• 3800 個の壁マスが置かれたら、このグリッドを初期グリッドとして採用する。

この方法によって生成された初期グリッドのサンプル 50 個が、共有フォルダ にて配布されている。

なお、これらの配布されているグリッドが実際のテストケースに含まれているとは限らない。

制約

• 0 \leq X \leq 10^{18}
  • X はこの範囲からランダムに選ばれる整数である。
• グリッドの縦幅および横幅は 150 マスである。
• 初期グリッド G の壁マス # の個数は 3800 である。
• 初期グリッド G では、壁マスの周囲 8 マスには他の壁マスは配置されない。
• 整数 X および初期グリッド G は、解答コードの提出ごとに新しく生成される。

部分点

この問題には部分点が設定されている。

解答コードの提出ごとに新しく生成される 25 個のどのテストケースに対しても、

• 65000 回以下の「操作」によって正答した場合は、 10 点
• 6500 回以下の「操作」によって正答した場合は、上に加えて 390 点

が与えられる。

提出

encode プログラムと decode プログラムを 1 つにまとめ、提出せよ。

後述する「ジャッジ」をみればわかるように、提出されたプログラムは encode 用と decode 用に 1 回ずつ起動される。

プログラム起動時には、符号化と復号のどちらを行えばよいかを判別するための文字列が入力される。

入力 （encode プログラム）

入力は以下の形式で標準入力から与えられる。

1 行目には文字列 encode が与えられる。

2 行目には X が入力され、 3 行目以降には G が入力される。

G のマス (i, j) は文字 G_{i,j} で表わされる。

• マス (i, j) が空マスのとき G_{i,j} は文字 . であり、
• マス (i, j) が壁マスのとき G_{i,j} は文字 # である。

文字の間に空白は含まれない。

encode
X
G_{1,1}G_{1,2}...G_{1,150}
:
G_{150,1}G_{150,2}...G_{150,150}

出力 （encode プログラム）

標準出力へ以下の形式で H を出力せよ。

H のマス (i, j) を文字 H_{i,j} で表せ。

• マス (i, j) が空マスのとき H_{i,j} は文字 .、
• マス (i, j) が壁マスのとき H_{i,j} は文字 #、
• マス (i, j) がSマスのとき H_{i,j} は文字 S とせよ。

文字の間に空白を含めてはいけない。

H_{1,1}H_{1,2}...H_{1,150}
:
H_{150,1}H_{150,2}...H_{150,150}

入出力 （decode プログラム）

最初に、文字列 decode が次の形式で標準入力から与えられる。

decode

その後、何回か「操作」を行う。「操作」では次の形式で標準出力へ出力せよ。

ロボットに移動させたい方向を文字 C で表せ。C は文字 U,D,L,R のいずれかであり、それぞれ上下左右の 4 方向を表す。

? C

この「操作」に対する応答は、次の形式で標準入力から与えられる。

ロボットがSマスにいるかどうかが文字 J で表される。

• ロボットがSマスにいるとき J は S であり、
• ロボットがSマスにいないとき J は . である。

J

最後に X を以下の形式で出力せよ。

! X

ジャッジ

ジャッジは以下の手順で行われる。

• 整数 X および初期グリッド G を生成する。
• 提出されたプログラムのプロセスを encode 用として立ち上げる。
• encode 用のプロセスに入力を与える。ただし、EOF は与えない。
• encode 用のプロセスから適切な出力があり、かつ encode 用のプロセスが終了するまで待機する。
• 不適切なグリッドが出力された場合は誤答とする。
• 提出されたプログラムのプロセスを decode 用として立ち上げる。
• decode 用のプロセスと対話を行う。この対話は decode 用のプロセスが終了するまで続く。
• 実行時間制限内に decode 用のプロセスから正しい出力がなされた場合のみ正答とし、それ以外は誤答とする。

注意

• 出力の度に標準出力を flush せよ。そうしない場合、TLE となる可能性がある。
• グリッド H および整数 X を出力した後は、プログラムをすぐに終了せよ。従わない場合のジャッジの挙動は未定義である。
• 出力形式が正しくない場合のジャッジの挙動は未定義である。
• プロセスは、上記によって規定された以外のいかなる通信も行ってはならない。

入力例（encode プログラム）

この例では G は 20 行 20 列のグリッドとして入力されているが、実際には 150 行 150 列である。

また、 この例では G の壁マスの個数は 70 個だが、実際には 3800 個である。

encode
239
#..............#..#.
......#....#.#......
..#............#....
.....#..#..#.#...#..
.#.#...............#
.......#..#..#......
..#..#.........#.#.#
..........#..#......
..#..#..........#.#.
.......#.#..#.......
...#..........#...#.
.#...#...#.#........
.......#.....#.#..#.
#.#......#.#........
....#.#.......#..#..
.........#.........#
#..#.#.#...#.#.#.#..
...................#
..#.....#.#.#.......
.....#.........#.#..

出力例 （encode プログラム）

この例では H は 20 行 20 列のグリッドとして出力されているが、実際には 150 行 150 列である。

####################
#S...###############
..##...#############
######.#############
#####..#############
#.....##############
..######....########
.#####...##..#######
.##########..#######
......####..########
########...#########
##########.#.....###
####..##...#.###..##
#####....###.####..#
############..####.#
#############......#
##################.#
############..###..#
#############.....##
####################

入出力例 （decode プログラム）

符号化が上記の入出力例のように行われた後の復号の例を示す。

decode

? R

.

? U

.

? L

S

! 239