A - カードの回収 Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MB

問題文

20\times 20 マスの盤面上に100枚のカードが置かれています。 一つのマスには高々一枚のカードが置かれています。 それぞれのカードには 0,1,\ldots,99 の数字が一つ書かれており、同じ数字のカードはちょうど一枚だけ存在します。

あなたの目的は高橋くんロボを操作してカードを全て回収し、最終的に回収したカードの山(山札と呼びます)が下から順に 0,1,\ldots,99 の順番になるようにすることです。 高橋くんロボは以下の命令からなる命令列を与えることで操作します。

  • U: 上に1マス移動する。現在位置が一番上のマスの場合は無効な操作となる。
  • D: 下に1マス移動する。現在位置が一番下のマスの場合は無効な操作となる。
  • L: 左に1マス移動する。現在位置が一番左のマスの場合は無効な操作となる。
  • R: 右に1マス移動する。現在位置が一番右のマスの場合は無効な操作となる。
  • I: 現在位置のマスに置かれているカードを回収して山札の一番上に置く。現在位置のマスにカードが置かれていない場合は無効な操作となる。
  • O: 山札の一番上のカードを現在位置のマスに置く。山札が0枚の場合や、現在位置に既にカードが置かれている場合は無効な操作となる。

高橋くんロボは初期状態で山札が0枚の状態で一番左上のマスの上に居ます。 命令列を全て実行し終えた段階で山札が下から順に 0,1,\ldots,99 となっていれば、ミッション成功となります。 移動命令(U,D,L,R)の回数が出来るだけ少ない命令列でミッションを成功させてください。

移動命令の回数を k とすると、4000-k のスコアが得られます。 カードの回収・設置命令(I,O)の回数はスコアに影響しないことに注意してください。 k が4000を超えた場合、命令列の長さが10000を超えた場合、無効な操作が行われた場合、もしくはミッションに失敗した場合のスコアは0点となります。

操作の例

高橋くんロボが一番左上のマスに居る状態でRRDDIUULLIRIという操作を行うと、0,1,2という順番でカードを回収し、移動命令の総数は9となります。

別の方法として、IRIRODOという操作を行うと、まず1,2という順番でカードを回収し、2,1という順番で置き直すことで下図のような状態になります。

ここからさらにDIUIUIという操作を行うと、0,1,2という順番でカードを回収し、移動命令の総数は先程より少ない6となります。

入力

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

x_0 y_0
x_1 y_1
\vdots
x_{99} y_{99}

数字 i の書かれたカードは一番左上のマスから下に x_i、右に y_i 移動した先のマスに置かれていることを表し、0\leq x_i,y_i\leq 19 を満たす。

出力

高橋くんロボを操作する命令列を空白や改行を含めずに一行で出力せよ。

入力生成方法

カードの配置はランダムに生成される。 具体的には (0,0),(0,1)\ldots ,(19,19) の長さ400の座標列をランダムシャッフルし、各 i=0,1,\ldots,99 に対して i 番目の座標に数字 i が書かれたカードが置かれる。

入力例 1

15 19
8 1
3 13
2 19
17 10
14 3
3 2
19 4
6 2
18 1
4 4
3 10
0 15
2 5
10 7
6 3
19 12
1 0
19 3
4 1
0 6
10 18
12 12
8 13
6 4
10 2
6 12
2 0
0 11
6 9
8 3
13 9
9 0
11 17
9 4
12 1
1 18
19 19
9 9
2 11
8 19
18 3
2 15
8 16
16 2
4 5
14 4
9 3
15 13
3 0
8 11
15 4
0 7
12 19
18 7
12 17
8 2
6 0
1 7
17 0
16 10
1 6
10 5
4 14
12 7
6 11
6 6
14 19
15 15
17 16
1 12
7 9
2 7
4 7
1 4
5 3
0 17
17 3
5 13
9 16
12 13
11 12
15 18
0 10
19 6
12 4
10 8
15 1
10 13
17 15
1 5
15 14
19 5
17 7
2 18
5 7
12 6
3 6
19 7
1 16

出力例 1

DDDDDDDDDDDDDDDRRRRRRRRRRRRRRRRRRRIUUUUUUULLLLLLLLLLLLLLLLLLIUUUUURRRRRRRRRRRRIURRRRRRIDDDDDDDDDDDDDDDLLLLLLLLLIUUULLLLLLLIUUUUUUUUUUULIDDDDDDDDDDDDDDDDRRIUUUUUUUUUUUUULLIDDDDDDDDDDDDLIUUUUUUUUUUUUUURRRIURRRRRRIUUURRRRRIDDLLLLLLLLLLIDDDDDDDDRRIUUUULLLLIDDDDDDDDDDDDDRRRRRRRRRIUUUUUUUUUUUUUUUUUULLLLLLLLLLLLIDDDDDDDDDDDDDDDDDDRRRIUUUUUUUUUUUUUUULLIUUUURRRRRIDDDDDDDDDDRRRRRRRRRRRRIDDLLLLLLIUUUURIUULLLLLLLLLIDDDDLLIUUUURRRRRRRRRRIUUUULLLLLLLLLLLLIUURRRRRRRRRRRIDDDDDDLLIDDLLLLLLIDDDDDRRRRRRIUUUULLLLLLLLLIDDRRRRRRRRRRRRRRRRRIUULLLLLLLLLLLLLIDDDLLLIUUUUUUUUUUURRRRRRRRRRRRRRRRRIDDDDDDDDDDDDDDDDDDRIUUUUUUUUUULLLLLLLLLLIUUUUUUURRIDDDDDDRRRRRRRRIDDDDDDDDDDLLLLLLLLLLLLLLLLIUUUUUUUUUUUUUUUURRRRRRRRRRRRIDDDDDDRIDDDDDDDDLLLLLLLLLLLLLLIUUUUUUUUUUUURRRIDDDDDDDDDDLIUUUUULIDDDDDDRRRRRRRRRRIUUUUUUUUUUUULLLLLLLLLLLLLIDDDDDRRRRRRRRRRRIDDDDDDDLLLLLLLIUUUUUUUUUUUUUUURRRIDDDDDDDDDDDDRRRRRRRRRRRRIDDDDDDLLLLLLLLLLLLIUUUUUURRRRRRRRRRIUUUULLLLLLLLLLLLLLLIUULLIUUUUURRRRRRRIDDDDDDDDDDDDDDDDLLLLLLLIURRRRRRRRRRIUUUUUUUUUUUUUUULLLLIDDDDDDDDDLIUUUUUURRRRRRRRRIDDDDDDDDLLLLLLLIUUUUUURRRRILLLLLIDDDDDDDDRRRRRRRRRRRRRIDLLLLIDDRIUUUUUUUUUUUUUUUULLLLIDDDDDDLLLIUUUUULLIDDIUUULLLIDDDDLIUUUUURRRRRRRRRRRRRRIDDDDDDDDDDDDDDDDDLLLLLLLLLLLLLLIUUUUUUUUUUUURRRRRRRRRRIDDDDRRRIDDDLLLIULIDDDDRRRRRRIUUUUUUUUUUUUUUULLLLLLLLIDDDDDDDDDDDDDDDDDDDLLLLIUUUUUUULLIUURRRRIDDDDDLLLLLLLIUUUUURRRRRRRRRRRRIDDDDDDDRRIUUUUUUUUUUUUUUUULLLLLLLLLLIDDDDDDDDDDDDDDRRRRRRRRRIDDDDLLLLLLLLLIUURRIUUUUUUUUUUUUUUURRRRRRRRRRRIDDDLLLLLLLLLLLIDDDDDDDLIUUUUUUUUUIDDDDDDDDDDDDDDDDRIUUUUUUUUUUUUUUUUUURRRRRRRRRI