問題文

H 行 W 列のマスからなるマップがあります。そのうち K 個のマスには、1台の車があります。

一番上の行を 1 行目、一番左の列を 1 列目とし、r 行 c 列にあるマスを (r, c) と表します。

K 台の車それぞれに、最初にいるマス（初期マスと呼ぶ）と目的地となるマス（目的マスと呼ぶ）が与えられます。車 i の初期マスは (A_i, B_i) です。また、車 i の目的マスは (C_i, D_i) です。 あなたはそれぞれの車に対して、各時刻 t (0 \leq t \lt L, tは整数) で辺で隣接したマスへの移動を指示できます。すると、時刻 t+1 で、その車は指示されたマスに移ります。ただし、以下のような移動を指示することはできません。

• 移動先のマスに時刻 t の時点で車が存在する場合
• 同時に複数の車の移動先が同じマスになる場合
• 移動先がマップの外側になる場合

1回の指示で、K 台全ての車それぞれに対して、隣接した4方向への移動を指示、あるいは、移動せず、今いるマスに留まることを指示します。最大で T 回指示を出すことができます。

各テストケースの得点および、この問題の得点は、次のように計算されます。

• あるテストケースでの車 i の最終的な位置を (r_i, c_i) として、 とします。
• 指示回数を L (0 \leq L \leq T) として P_T = 10 + L \times 0.01 とします。
• score = 10^7 / (P_D \times P_T)
• 上記の計算で算出した score の小数点以下を切り上げたものが、そのテストケースでの最終的な得点となります。
• テストケースは全部で 30 個あります。各テストケースの得点の合計が、この問題の得点になります。

適切に指示を出すことで、得点を最大化してください。

入力例1

6 6 2 100
3 3 4 5
6 2 2 4

注意: この入力はテストケースとしての制約を満たしていません。

車1の初期マスを 1、車1の目的マスを X、車2の初期マスを 2、車2の目的マスを Y としたマップを以下に図示します。

出力例1

4
RR
RU
DU
-L

全ての指示を実行後のマップは以下のようになります。車1は目的マスに到着しています。

• 時刻 0 では車1も車2も右に移動します。
• 時刻 1 では車1は右に、車2は上に移動します。
• 時刻 2 では車1は下に、車2は上に移動します。
• 時刻 3 では車1は移動しません。車2は左に移動します。
• この出力によって得られるスコアは、以下のように計算されます。
  • 車1の目的マスは (4,5) で、最終的な位置は (4,5) です。
  • 車2の目的マスは (2,4) で、最終的な位置は (4,2) です。
  • よって P_D は 20+ (|4-4|+|5-5|)+(|2-4|+|4-2|)=24 です。
  • P_T は 10 + 4 \times 0.01=10.04 です。
  • このテストケースでの得点は 10^7 / (24 \times 10.04) = 41500.6… を切り上げた 41501 となります。

入力例2

30 30 450 10000
12 11 24 29
17 16 6 26
29 8 25 18
11 27 28 19
16 16 24 28
27 17 6 12
4 11 14 28
27 21 9 12
21 10 26 26
24 20 11 12
16 23 12 15
3 21 11 9
7 2 22 30
20 18 18 7
4 29 22 1
7 13 12 19
4 17 21 10
23 10 27 29
6 29 21 21
17 22 10 7
12 9 13 25
18 24 8 10
15 29 22 29
8 15 1 23
1 18 11 7
17 28 30 25
25 26 12 7
9 7 15 18
17 3 3 8
18 20 11 5
20 1 25 13
18 8 16 4
4 5 15 22
2 13 24 24
7 30 6 28
10 16 2 14
19 7 9 17
13 26 5 24
10 25 30 6
4 12 26 15
30 16 25 14
24 4 6 5
24 13 12 26
24 21 5 1
20 27 1 24
6 7 17 20
22 3 10 19
18 15 12 23
7 24 6 10
3 23 27 12
16 27 1 7
17 13 16 15
18 10 2 29
10 9 8 27
9 1 19 29
16 13 17 6
25 16 7 1
18 6 12 17
26 14 20 16
2 9 9 13
22 2 16 16
12 28 15 17
11 5 25 2
11 29 8 21
25 9 17 27
5 19 4 9
13 29 22 25
30 28 11 20
9 5 1 2
6 11 21 30
22 13 22 20
6 28 19 6
11 24 5 15
29 24 5 14
21 29 25 10
18 21 14 6
2 8 17 30
6 16 26 8
9 30 11 26
11 7 20 23
18 19 6 6
16 4 27 4
7 22 8 28
2 4 5 6
30 20 4 11
15 5 9 18
12 21 30 23
20 25 18 14
8 11 9 28
8 17 26 11
30 9 30 29
14 11 24 15
17 6 4 17
4 23 14 26
18 7 14 12
29 10 9 22
20 22 17 18
26 23 17 8
23 16 7 16
3 16 22 28
16 15 27 19
8 3 29 2
28 21 16 5
19 19 13 17
2 30 12 25
28 23 13 16
6 24 6 19
8 22 24 22
20 29 10 16
7 26 27 9
1 21 2 24
25 30 1 30
17 23 28 16
10 13 23 29
19 14 25 11
16 11 6 29
13 2 4 1
20 4 9 27
11 15 2 15
22 26 10 23
23 7 11 1
6 17 3 2
18 14 16 13
24 28 1 13
8 30 26 29
9 24 8 7
21 30 25 26
26 11 9 29
21 14 30 8
28 17 28 12
3 5 28 13
21 22 21 7
30 13 24 6
24 10 15 4
28 16 5 18
24 11 18 24
24 12 1 17
20 11 3 7
30 29 17 17
12 5 19 10
19 24 30 27
29 3 1 10
4 3 21 22
15 16 17 16
1 28 6 4
30 6 23 14
12 26 4 23
6 25 23 12
4 26 25 9
13 22 29 16
19 20 6 22
4 14 12 4
17 14 4 12
13 7 20 8
29 12 15 27
2 25 22 6
12 3 28 3
7 18 19 20
18 9 13 24
10 11 8 19
29 25 9 4
11 3 20 28
14 24 11 23
19 8 25 6
14 10 1 29
9 29 28 4
16 5 27 3
10 12 2 9
9 19 7 23
15 18 10 1
6 27 13 21
4 30 30 2
1 1 28 5
24 2 14 15
29 19 12 3
12 22 14 14
25 28 9 30
15 8 11 11
15 14 19 11
19 10 29 26
21 21 2 22
24 1 11 28
30 30 8 1
28 5 26 3
4 8 19 27
6 30 11 3
19 15 22 5
16 28 5 29
2 5 23 9
26 25 25 19
17 5 7 22
18 1 3 19
28 14 6 1
10 21 8 13
14 28 18 26
9 8 16 24
11 25 4 4
28 11 24 13
30 3 24 9
3 9 6 30
16 20 3 3
11 9 23 4
15 6 12 16
13 23 12 24
25 19 28 1
5 24 27 28
28 10 26 25
27 20 15 2
17 20 21 14
3 6 19 3
17 11 21 6
1 29 2 4
25 17 29 15
22 24 12 30
22 27 6 23
6 19 30 19
13 16 30 28
14 1 6 18
27 16 6 3
8 26 9 26
18 4 23 13
16 30 14 1
20 6 10 6
12 24 3 10
19 1 24 16
5 11 7 2
2 20 29 8
18 2 16 1
4 24 22 8
17 8 27 16
19 22 24 27
22 28 9 23
1 10 12 10
12 4 3 13
8 1 11 24
3 7 13 9
21 3 1 12
30 1 26 6
1 16 13 8
10 17 24 20
6 9 5 21
22 21 5 5
10 20 16 27
5 18 18 16
16 12 23 26
25 22 12 6
29 27 6 17
15 19 23 30
2 3 25 27
5 28 8 3
15 20 12 9
15 4 25 7
9 12 7 4
24 30 25 4
20 5 3 5
6 2 20 25
15 23 23 28
26 26 7 25
23 27 27 2
5 27 30 12
21 1 26 13
23 24 10 11
5 29 3 6
2 19 5 11
22 7 5 19
20 17 27 26
14 23 25 22
21 15 19 30
28 19 1 27
27 30 25 5
23 17 14 7
27 5 17 2
26 30 29 5
7 12 14 21
9 3 15 3
8 24 19 28
3 3 7 11
2 26 10 26
30 10 21 11
1 3 22 23
10 28 2 7
19 27 14 24
28 24 30 13
21 9 14 2
15 28 2 23
5 6 10 13
27 18 16 2
17 18 10 28
19 11 20 26
13 11 16 21
15 25 24 3
3 24 22 24
1 8 11 15
15 15 23 2
26 15 29 1
1 14 20 15
28 1 4 20
7 10 3 11
14 5 25 1
29 11 13 26
25 29 8 5
18 27 17 3
22 14 25 16
17 7 19 8
25 23 30 1
23 23 12 13
26 24 10 17
8 4 12 8
17 30 7 24
29 2 20 10
7 1 3 23
26 9 29 23
23 15 30 7
27 9 15 21
25 4 1 25
8 14 23 17
23 12 19 7
13 27 27 14
5 15 27 17
16 22 10 21
1 4 3 27
12 29 21 2
24 15 29 17
21 8 23 18
12 17 30 18
28 20 11 17
23 18 21 27
13 5 5 4
14 2 6 24
1 12 28 10
14 27 18 25
27 4 30 26
16 2 7 28
5 20 28 8
3 17 20 9
1 25 21 16
26 19 11 30
4 20 25 8
10 15 20 17
6 5 19 26
20 14 24 5
1 7 21 9
13 15 30 15
23 2 7 8
15 1 1 18
19 17 10 18
16 10 21 15
23 21 6 14
8 25 1 1
21 18 13 18
9 4 24 11
18 28 17 1
27 3 25 24
20 9 10 15
30 11 13 11
13 28 29 14
17 25 23 1
15 12 16 10
19 18 13 23
1 19 2 6
8 7 8 30
22 12 6 7
8 2 16 9
17 26 7 26
3 30 14 19
4 4 28 27
13 12 20 1
9 6 15 13
24 24 2 28
21 20 26 17
29 29 25 28
23 28 30 9
16 21 29 18
22 15 27 27
5 12 20 13
26 7 11 8
12 7 13 2
16 25 15 9
20 20 13 6
16 3 21 17
8 27 17 11
18 12 12 5
4 18 9 2
1 2 28 30
15 17 18 6
17 24 26 5
16 9 20 12
30 14 22 4
19 5 21 8
12 15 9 10
6 8 2 20
25 2 6 27
30 7 13 5
6 26 16 29
10 30 7 12
9 28 23 16
3 13 30 11
27 19 30 17
1 5 9 16
10 3 14 11
19 30 8 4
3 10 2 21
1 15 8 16
29 4 18 13
6 12 28 15
7 27 24 26
26 10 7 6
12 8 14 4
4 16 5 2
13 18 21 19
26 18 3 16
24 7 6 20
3 15 19 23
20 16 19 16
14 6 27 30
13 30 1 28
14 30 20 11
23 29 8 11
9 2 1 5
27 25 30 4
18 3 22 9
8 10 21 4
7 20 30 22
14 20 16 20
22 29 5 20
24 19 12 20
28 13 11 16
21 7 12 29
21 5 14 8
12 19 1 3
10 4 15 23
2 11 14 18
25 25 15 28
22 9 13 30
27 6 9 15
15 13 25 30
25 13 16 23
7 29 10 10
17 9 28 23
11 1 19 14
21 13 12 18
27 2 6 21
20 30 23 21
11 14 20 7
26 8 4 28
5 16 15 25
18 26 7 19
22 1 19 19
20 12 4 8
7 7 3 14

ジェネレータに seed=1 を指定することで同じ入力が得られます。

出力例2

2
RRUL---UD--DR-LR---DD--RD-UD--R-D--UDLL-LRR-L-RR-LLDRRD-L---ULUL-U-U-D--LL---L-RLDRDL-DLDDU-UD---LU-D-RD-ULDU-R-DRLUUU-LLU-LLL-R----ULLUD--RRUD-DULDLDRD--UDDD-D-RRDU---UD-DDRL--RDDU-UL--DRR--UUU-R-URDL-RR-R-U-D-DRUUDRULDRU-LRLDU--RUD--RURDDRLDD-UU--------RRDLL---DRD-R-LUULD--LD--LL---D-RR---R-RDULL-UUD--LURLUU--RRD---U--R---ULRLD-LD-L---DLDDRRU-L----UUR-----RL--LDDDRLU-D-RU-L---U-DD--URLURU-LLD-R-URDRR-UD-DLRDURULR-DDLRURUU-RL-R--U-RLRD-U-LU-LD-R
DRU-DLDU-LUDRLLR-DDU-D-UL--D-L--DD--U-DDUURULDR-ULU-RURD--R-RL-L-D-L-D--LLD--LDD--DDLRR-DDD-R---U---D-LUDULDL-D--DR-UU-LUD-UR--RDLDLUU-DRULD-U--DUL--L-------DR-RRL-U-L-RU--DRLLRUUD-RLD--L-DLR--LLDURRR-DR--DRU-D--DRLUDR---U---LUUD-DUDRDRRR--RUDD--L-RL----U--UL-DL-LD--U-L--LR-DDD--LRDU-DD---D-RD-DRR-RL---LUUR--RD-URRUL-LRLD--U---DDRUD-L-DR--DLRU-R---ULRRL---LL-U--DDRD-DL----U--U-L-D-ULDU-L-RU-LR--RDU-DUD-RD-RU---LU-L----DD-----U-DR-R--D-U-ULL-DRR-U

ジェネレータとテスター

ジェネレータとテスターを次のリンクから提供しています。

ジェネレータ・テスター

ビジュアライザ

入力ファイルと出力ファイルから、得点の計算および結果を可視化するビジュアライザを用意しました。

• このビジュアライザは主要なブラウザ上で動作確認を行っていますが、全ての環境で動作することを保証していません。
• このビジュアライザ上で計算された得点は、当コンテストでの得点ではありません。解答を AtCoder 上で提出する事によって採点が行われます。また、ビジュアライザ上で計算された得点は、当コンテスト上での得点を保証するものではありません。
• このビジュアライザを使用することによるあらゆる損害は保障しかねますので、予めご了承ください。

ビジュアライザは次のリンクからも提供しています。使用法についてもリンク先に記述があります。

ビジュアライザ