AT_s8pc_5_g Snake Escaping 2

[problemUrl]: https://atcoder.jp/contests/s8pc-5/tasks/s8pc_5_g 22XX 年, AtCoder 王国には、毒蛇が大量に発生していた. 国王の chokudai は, 毒蛇を駆除するため, 見つかった毒蛇を全て倉庫の中に閉じ込めていたが, 3 年後, 再び毒蛇が王国に発生するようになっていた. 王国の square 公園には, 色が書かれているタイルがある. タイルは $ H $ 行 $ W $ 列のマス目と考えてもよい. 毒蛇はタイルの色に擬態することによって, 再び倉庫に入れられないように逃走することにした. さて, 今日も $ 1 $ つの毒蛇が公園に脱走していた. 毒蛇は $ |S| $ 個の節を持ち, 先頭から $ i $ 番目の節の色は, 文字列 $ S $ の $ i $ 文字目である. $ S $ は `R`, `G`, `B` から成り, それぞれ赤, 緑, 青を意味する. この公園では, 毒蛇の隣り合った節は必ず上下左右に隣りあったマスにあるようにする. 取り敢えず, 毒蛇は「再び倉庫に入れられない」ことを信じたいので, あなたに, どんなタイルの状態と毒蛇の位置の組み合わせにおいて, 完全に擬態する, すなわちどの毒蛇の節もそのマスのタイルと同じ色となることができるかを教えてもらいたい. その時, 毒蛇の色が与えられるので, あり得るタイルの色と毒蛇の位置の組み合わせを答えよ.

入力は以下の形式で標準入力から与えられる. > $ S $

出力は以下の形式に従うこと. > $ H $ $ W $ $ a_{1,1} $$ a_{1,\ 2} $ ... $ a_{1,\ W} $ $ a_{2,1} $$ a_{2,\ 2} $ ... $ a_{2,\ W} $ : : : $ a_{H,1} $$ a_{H,\ 2} $ ... $ a_{H,\ W} $ $ sx $ $ sy $ $ V $ - $ 1 $ 行目には, 公園の縦の長さ $ H $, 横の長さ $ W $ を出力すること. - $ 2 $ 行目から $ H $ 行にわたって, 公園の状態 $ a_{i,\ j} $ を出力すること. $ a_{i,\ j} $ は `R`, `G`, `B` のどれかでなければならない. - $ H+2 $ 行目には, 毒蛇の先頭の位置 ($ sx $, $ sy $) を出力すること. $ 1\ \leq\ sx\ \leq\ H $, $ 1\ \leq\ sy\ \leq\ W $ でなければならない. - $ H+3 $ 行目には, 毒蛇の $ 2 $ 個目の節以降の動き方を出力すること. $ i $ 節目が $ i-1 $ 節目の左にある場合 `L`, 右にある場合 `R`, 下にある場合 `D`, 上にある場合 `U` と出力すること. - **$ H $, $ W $ は $ 100 $ 以下でなければならない.**

### 制約 - $ S $ は `R`, `G`, `B` から成る, $ 1 $ 文字以上 $ 1\ 000\ 000 $ 文字以下の文字列である. - **$ S $ は, `R`, `G`, `B` が等確率で出現するようにランダムに作られた文字列である.** ### 小課題 小課題 $ 1 $ \[$ 80 $ 点\] - $ |S|\ \leq\ 10\ 000 $ を満たす. (10 ケース) 小課題 $ 2 $ \[$ 320 $ 点\] - $ |S|\ \leq\ 15\ 000 $ を満たす. (10 + 10 = 20 ケース) 小課題 $ 3 $ \[$ 800 $ 点\] - $ |S|\ =\ 1\ 000\ 000 $ を満たす. (20 ケース) ただし, 小課題 3 における得点は以下のように計算される. - 全てのテストケースのうち最も大きかった $ max(H,W) $ の値を $ L $ とおく. その時, 得点は以下のようになる。 - $ L\ \leq\ 30 $ のとき, $ 800 $ 点. - $ 31\ \leq\ L\ \leq\ 40 $ のとき, $ 1470\ -\ 24L $ 点. - $ 41\ \leq\ L\ \leq\ 50 $ のとき, $ 1270\ -\ 19L $ 点. - $ 51\ \leq\ L\ \leq\ 100 $ のとき, $ floor(620\ \times\ 3^{1-\frac{L}{30}}\ +\ 20) $ 点. また, すべての $ 30\ \leq\ L\ \leq\ 100 $ に対する小課題 3 の得点は, [このリンク](https://drive.google.com/file/d/1Ycjp29PZ0EdbxKb4tVo2uf58jhBGwGF1/view?usp=sharing) からも見ることができる. ### Sample Explanation 1 例えば, 以下のように擬態できる. !\[ \](https://img.atcoder.jp/s8pc-5/a3a4600450c246a638c6d391c88825e8.png) ### Sample Explanation 2 例えば, 以下のように擬態できる. !\[ \](https://img.atcoder.jp/s8pc-5/ef60b421a9ec73374398dfd4c9f04350.png)