問題文

命令列を読み込んでボードの上を歩くロボットがあります。この問題では、命令 とは S, L, R の 3 種類の文字であり、命令列 とはこれらの文字からなる文字列です。

長さ L (= 300) の命令列が N (= 500) 個与えられます。あなたのタスクは、M \times M (M = 29) マスのボードを構築して、N 個の命令列に対してロボットをできるだけバラバラな位置で停止させることです。

ロボットはボードの中央のマス (上から 15 マス、左から 15 マス目) から上を向いて動作を開始し、命令列に含まれる命令を左から順に実行していきます。それぞれの命令の効果は次の通りです。

• S : 現在向いている方向に 1 マス進みます。
• L : 90 度左に回転します。
• R : 90 度右に回転します。

ただし、あなたはこれらの命令の効果に影響を及ぼすマスを使ってボードを構築することができます。使うことのできるマスは以下の通りです。

• . : 通常マスです。このマスの上で実行された命令は本来の効果を発揮します。
• # : 壁マスです。ロボットがこのマスに進入しようとしたとき、その移動は失敗し、ロボットは手前のマスから動きません。なお、ボードの最も外側のマスはすべて壁マスでなければいけません。
• D : 2 倍マスです。このマスの上で実行された命令の効果が 2 回連続で発揮されます (途中で通過したマスの効果は無視されます)。
• T : 3 倍マスです。このマスの上で実行された命令の効果が 3 回連続で発揮されます (途中で通過したマスの効果は無視されます)。
• L : Lマスです。このマスの上で命令 R が実行されると、通常マスの上で L が実行されたときと同じ効果が発揮されます。
• R : Rマスです。このマスの上で命令 L が実行されると、通常マスの上で R が実行されたときと同じ効果が発揮されます。

これらのマスはそれぞれ何個でも使うことができます。

あなたのタスクを再度述べると、N 個の命令列に対してロボットができるだけバラバラな位置で停止するようなボードを構築することです。 より具体的には、あなたが構築したボードには以下のように点数が与えられます。

• 各マスの 停止カウント を 0 とする。
• 各命令列に対し、中央のマスからロボットにその命令列を実行させ、実行終了時にロボットが立っているマスの停止カウントを 1 増やす。
• 各マスに対する点数を以下のように定める。
  • 停止カウントが 1 のとき、そのマスの点数は 10 点である。
  • 停止カウントが 2 のとき、そのマスの点数は 3 点である。
  • 停止カウントが 3 のとき、そのマスの点数は 1 点である。
  • 上記以外のとき、そのマスの点数は 0 点である。
• すべてのマスに対する点数の和がそのボードの点数となる。

できるだけ高い点数を得るボードを構築してください。

制約

• N = 500
• M = 29
• L = 300
• S_i は長さ L の文字列である。
• S_i の文字は 1 文字ずつ独立に選ばれ、50% の確率で S、25% の確率で L、25% の確率で R となる。

入力

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

N M L
S_1
S_2
:
S_N

出力

できるだけ高い点数を得るボードを以下の形式で出力せよ。

T_1
T_2
:
T_M

ここで T_i はそれぞれ長さ M の文字列であり、., #, D, T, L, R 以外の文字を含んではならない。

また、ボードの最も外側の文字 (すなわち、T_1, T_M のすべての文字と各 T_i の最初と最後の文字) はすべて # でなければならず、T_{15} の 15 文字目は # であってはならない。

採点

単一のテストケースにおける点数は、問題文で述べた方法で算出される。

テストケースは 30 ケース与えられ、全てのテストケースの点数の和がその提出の得点となる。

なお、example_01 以外のケースで 1 ケースでも出力が不正であった場合、example_01 以外のケースの点数はすべて 0 点となる。

入力例0

6 7 7
RSLSSRS
RSSLSSS
SRSLLLL
RSLSLLL
LSLSLLL
RRSRSRR

この入力は例示用の小さいサイズのものであり、制約を満たしません。

出力例0

#######
#....##
#..L..#
#.T...#
#..D..#
#R....#
#######

各命令列に対し、ロボットが停止するマスは以下のようになり、60 点を獲得できます。

#######
#.5.1##
#.3642#
#.....#
#.....#
#.....#
#######

入力例1

入力ファイルと出力例はこちらから(zip)

採点結果の「example_01」はこちらのデータとなります。このデータも採点対象です。