/ 
Time Limit: 1 sec / Memory Limit: 256 MB
配点：1200 点
問題文
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 の得点は, このリンク からも見ることができる.
入力例 1
RGB
出力例 1
3 3 RGB RGB RGB 1 1 RR
例えば, 以下のように擬態できる.
入力例 2
GBRBGBR
出力例 2
4 3 GBR RGR RBR RRR 1 1 RRLDDD
例えば, 以下のように擬態できる.
入力例 3
RGBGRGRBRR
出力例 3
3 4 RGBG BRGR RRRR 1 1 RRRDLLLRD
Max Score：1200 points
Problem Statement
In the year 22XX, there were many poisonous snakes in AtCoder Kingdom. The king of AtCoder Kingdom, chokudai, locked all poisonous snakes he found in storage to exterminate this snake, but three years later poisonus snakes started to emerge again.
In Square Park in AtCoder Kingdom, there are H \times W colored squares (red, green, or blue) which forms a grid with H rows and W columns.
Some escaped snakes are going to try to mimic the colored squares in Square Park, to avoid getting caught by the king, chokudai.
Today, a poisonous snake escaped to Square Park. This snake is divided into |S| part from head to tail, and color of the i-th part is S_i. S consists of 'R', 'G', and 'B', and it denotes red, green, and blue, respectively.
If the snake is in Square Park, the adjacent parts should be in adjacent cells. The snake can mimic the colored squares completely if and only if every part of the snake has same color as the square that this part is in.
The snake wants to believe that itself will not be locked in the storage again, so the snake asked you to construct the coloring of Square Park and the placement of the snake.
Input
Input is given from the Standard Input in the following format:
S
Output
Print your answer in the following format:
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
- In 1st line, print the number of row H and the number of column W of Square Park.
- In j-th letter of i+1-th line (1 \leq i \leq H, \ 1 \leq j \leq W), print a_{i, j}, which denotes the color ('R', 'G', or 'B') of square (i, j).
- In (H+2)-th line, print sx and sy, where (sx, sy) is the coordinate of the 1st part of the snake.
- In (H+3)-th line, print string V with length |S|-1, whose i-th letter of V is the relation of place of i-th part and (i+1)-th part of the snake. If (i+1)-th part is at the left of i-th part, it is 'L'. For right, up, and down, it is 'R', 'U', and 'D', respectively.
- Note that H and W should be less than or equal to 100.
Constraints
- S is a string which consists of 'R', 'G', 'B' and the length is between 1 and 1 \ 000 \ 000 (inclusive).
- S is randomly generated (the occurrence of 'R', 'G', and 'B' is almost equal)
Subtasks
Subtask 1 [80 points]
- |S| \leq 10 \ 000. (10 cases)
Subtask 2 [320 points]
- |S| \leq 15 \ 000. (10 + 10 = 20 cases)
Subtask 3 [800 points]
- |S| = 1 \ 000 \ 000. (20 cases)
Scoring
Scoring in Subtask 3 is special.
Let L be the maximum value of max(H,W) among all subtask-3 cases. Your score will be calculated as follows:
- If L \leq 30, you will get 800 points.
- If 31 \leq L \leq 40, you will get 1470 - 24L points.
- If 41 \leq L \leq 50, you will get 1270 - 19L points.
- If 51 \leq L \leq 100, you will get floor(620 \times 3^{1-\frac{L}{30}} + 20) points.
You can see this google drive file to look scores of subtask 3 when 30 \leq L \leq 100.
Sample Input 1
RGB
Sample Output 1
3 3 RGB RGB RGB 1 1 RR
The snake can mimic as follows:
Sample Input 2
GBRBGBR
Sample Output 2
4 3 GBR RGR RBR RRR 1 1 RRLDDD
The snake can mimic as follows:
Sample Input 3
RGBGRGRBRR
Sample Output 3
3 4 RGBG BRGR RRRR 1 1 RRRDLLLRD