A - Durability-Constrained Transport Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

ストーリー

AtCoder社は、新しいオフィスへ移転することにした。 コストを抑えるため、引っ越し業者には頼らず、高橋社長自ら荷物の運び出しを行うことになった。

旧オフィス内には大量のダンボール箱が平積みされており、それらをすべて出入り口まで運び出す必要がある。 ダンボール箱は積み重ねて複数同時に運ぶことができるが、重ねすぎると重さに耐えきれず潰れてしまう可能性がある。

できるだけ少ない移動回数で、すべての箱を無事に運び出す方法を考えてほしい。

問題文

N \times N マスのオフィスがある。左上のマスの座標を (0, 0) とし、下方向に i、右方向に j 進んだ位置の座標を (i, j) とする。マス (0, 0) にはオフィスの出入り口がある。

初期状態では、出入り口を除くすべてのマスにダンボール箱が1つずつ置かれている。各ダンボール箱には、重さ と 耐久力 の2つの数値が定まっている。マス (i, j) にあるダンボール箱の重さは w_{i,j}、耐久力は d_{i,j} である。

ダンボール箱は上下に積み重ねることで、複数個を同時に運ぶことができる。高橋社長の目的は、初期位置 (0,0) から開始し、以下の操作を繰り返してすべてのダンボール箱をオフィスの外に運び出すことである。

  1. 現在位置にあるダンボール箱を手に持つ。すでにダンボール箱を持っている場合は、その一番上に乗せる。現在位置にダンボール箱がない場合は、この操作は行えない。
  2. 手に持っているダンボール箱の山の一番上を現在位置に置く。すでにダンボール箱が置かれているマスでは、この操作は行えない。
  3. 上下左右の隣接するマスに移動する。ダンボール箱が置かれているマスにも移動できるが、オフィスの外（N \times N の範囲外）に出ることはできない。

高橋社長は非常に力持ちで、どれだけ重いダンボール箱でも一度に持つことができる。一方で、手に持っているダンボール箱の耐久力は移動（操作3）するたびに減少する。耐久力が 0 以下になった箱は潰れてしまい、WA と判定される。

耐久力の減少量は、その箱の上に載っているダンボール箱の総重量に等しい。すなわち、現在持っているダンボール箱の重さを下から順に w_1, w_2, \ldots, w_n としたとき、下から i 番目（1 \le i \le n）の箱は \sum_{j=i+1}^n w_j だけ耐久力が減少する。

耐久力が減少するのは移動（操作3）のときのみであり、操作1や操作2では変化しない。また、操作2で箱を置いても、減少した耐久力は元に戻らない。

操作3によって出入り口のあるマス (0,0) に移動すると、手に持っているダンボール箱はすべてオフィスの外に運び出される。

操作は最大で 2\times N^3 回まで繰り返すことができる。できるだけ移動回数が少ない方法ですべてのダンボール箱を運び出してほしい。

得点

操作3（移動）を行った回数を T、オフィス内に残っているダンボール箱の個数を R とする。 このとき、以下の得点が得られる。

  • R>0 の場合、N^2-R
  • R=0 の場合、N^2+2\times N^3-T

ここで、T は操作3（移動）を行った回数であり、操作1（持ち上げ）および操作2（設置）は T に含まれない。 ただし、操作回数の制限（最大 2 \times N^3 回）には、すべての操作が含まれる。

合計で 150 個のテストケースがあり、各テストケースの得点の合計が提出の得点となる。 一つ以上のテストケースで不正な出力や制限時間超過をした場合、提出全体の判定がWAやTLEとなる。 コンテスト時間中に得た最高得点で最終順位が決定され、コンテスト終了後のシステムテストは行われない。 同じ得点を複数の参加者が得た場合、提出時刻に関わらず同じ順位となる。

入力

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

N
w_{0,0} \cdots w_{0,N-1}
\vdots
w_{N-1,0} \cdots w_{N-1,N-1}
d_{0,0} \cdots d_{0,N-1}
\vdots
d_{N-1,0} \cdots d_{N-1,N-1}
  • すべてのテストケースにおいて、N = 20 に固定されている。
  • w_{i,j} はマス (i, j) に置かれているダンボール箱の重さを表す整数である。(0,0) のマスにはダンボール箱が置かれていないため、w_{0,0} = 0 であり、それ以外のマスに対しては 1 \leq w_{i,j} \leq 10^3 を満たす。
  • d_{i,j} はマス (i, j) に置かれているダンボール箱の耐久力を表す整数である。(0,0) のマスでは d_{0,0} = 0、それ以外のマスに対しては 10 \leq d_{i,j} \leq 3\times 10^4 を満たす。

出力

t ターン目の操作を、1文字 a_t で以下のように表す。

  1. 操作1を行う場合：1
  2. 操作2を行う場合：2
  3. 操作3を行う場合：移動方向に応じて、上：U、下：D、左：L、右：R

操作回数を L としたとき、以下の形式で標準出力に出力せよ。

a_0
\vdots
a_{L-1}

例を見る

入力生成方法

  • \mathrm{rand\_double}(L,U): L 以上 U 以下の実数値を一様ランダムに生成する。

w の生成

(0,0) を除くすべてのマス (i,j) に対し、 w_{i,j}=\mathrm{round}(\mathrm{rand\_double}(1,\sqrt{1000})^2) により生成する。

d の生成

(0,0) を除くすべてのマス (i,j) に対し、 d_{i,j}=\mathrm{round}(w_{i,j}\times \mathrm{rand\_double}(10,30)) により生成する。

ツール(入力ジェネレータ・ビジュアライザ)

コンテスト期間中に、ビジュアライズ結果の共有や、解法・考察に関する言及は禁止されています。ご注意下さい。

入力例 1

20
0 3 749 809 20 263 83 30 559 8 5 269 675 47 235 204 747 216 134 244
2 651 130 557 93 426 690 873 506 98 22 251 213 814 874 79 857 6 158 639
2 965 45 107 259 20 957 244 18 962 152 82 327 226 24 131 99 1 255 60
177 1 42 878 353 185 89 656 757 54 351 349 489 249 679 756 191 395 719 145
613 203 741 455 1 402 877 791 146 956 506 262 280 746 156 733 66 237 389 115
164 738 84 747 10 579 81 6 78 215 337 556 479 498 2 674 120 737 429 106
872 394 35 325 49 6 129 185 45 218 18 892 162 7 419 579 768 11 724 266
29 236 832 372 132 857 840 10 446 74 734 199 148 802 24 467 321 410 237 50
715 391 412 13 312 2 138 645 333 260 621 736 483 876 62 9 44 77 180 3
165 852 738 29 110 119 857 974 104 103 886 500 271 819 155 467 579 108 466 837
243 39 711 197 494 17 800 721 15 193 138 5 451 736 311 272 582 177 112 533
441 65 2 544 545 259 147 10 101 411 23 144 449 18 668 211 497 475 470 867
179 661 8 73 600 371 374 417 150 629 520 236 625 508 168 733 36 282 427 121
534 715 558 187 707 714 368 882 437 607 27 18 15 988 306 198 130 343 70 42
248 257 714 3 133 859 658 52 385 487 572 25 211 485 381 453 198 496 576 7
18 89 103 218 494 679 981 133 59 69 73 397 517 567 542 8 619 13 247 373
355 745 81 291 401 142 357 244 7 581 440 6 963 173 750 763 1 382 278 5
275 103 7 843 2 14 86 374 97 218 15 319 55 503 886 44 27 228 375 796
430 146 873 39 5 714 366 732 679 369 642 344 978 237 230 98 273 98 58 850
266 608 739 2 190 592 194 84 611 14 101 909 4 582 122 12 122 994 635 916
0 89 10274 11922 300 6685 978 640 13718 132 143 7028 18239 1327 6881 2284 21156 2760 1998 5070
57 17805 2901 14519 1693 10841 11743 18976 9379 2092 285 3524 5983 16567 22972 1063 19938 131 4309 15177
40 21359 1207 2121 3421 233 27186 6872 310 11251 3786 1176 5352 4669 644 2427 1063 16 5886 1000
3615 18 918 12387 7059 4315 2057 15533 15664 1195 10141 8595 5218 6993 10755 19254 2432 9972 20357 3718
8450 3919 8454 5988 19 10140 12007 18903 3935 18739 11371 4330 3194 11908 1710 15085 1585 6893 5701 1207
2641 20082 1007 20670 242 16408 821 174 1941 6053 5509 10545 11073 13932 58 9389 3431 10249 5398 2521
19054 4835 829 4674 1201 126 2364 3885 858 5383 501 21304 4520 180 5604 9931 21101 168 19471 5338
712 5765 11653 9607 2457 18495 9954 105 11699 818 16356 3906 1654 10149 438 13133 7833 4447 5445 1326
10666 6309 4688 285 5169 40 1404 18295 3541 7125 8287 20290 8837 17858 1621 135 1115 1091 3288 54
2597 9955 16763 471 2335 1574 14642 16187 2376 1887 24636 5641 7433 17306 2957 6663 5966 3044 5358 9769
5905 611 17099 3300 11161 385 15895 19522 435 2108 3650 141 8058 21485 3988 2737 16273 4105 2571 11724
7296 1489 51 6519 5911 3647 2533 236 1190 4266 500 3338 7312 385 19463 4942 10835 11174 10700 9738
4477 16314 165 805 17700 4016 7057 12420 2756 17887 6796 5143 12927 6174 4740 20452 424 3101 11615 2445
13368 15983 15135 5582 12578 15525 4649 24252 6902 17168 460 228 413 23337 8237 3631 3838 6815 1706 1166
6713 5548 10910 65 1426 17897 8171 886 5466 8932 7274 277 2969 12341 10707 10334 2143 12639 7016 144
462 1829 1530 6394 14306 7206 16721 3469 1058 1201 1641 7989 7068 8612 8485 197 8113 306 6585 6213
4014 13889 2016 7397 6739 3985 10474 2701 107 8285 5588 90 10340 2717 16467 20426 22 9518 5965 124
6569 2065 136 23365 25 276 992 8245 1736 4797 316 6097 712 9186 25794 1282 431 3350 8782 9615
9031 3928 13928 394 118 18798 6870 18849 8115 10434 8884 3992 29004 6921 3450 2052 5705 2732 837 18597
6226 15329 13644 58 3923 10666 4191 1802 18180 242 2764 13987 101 10450 1509 311 1638 19358 11533 16943

出力例 1

D
R
1
R
R
1
U
1
L
1
L
1
L
R
R
R
R
R
R
R
R
1
D
1
L
1
L
1
L
1
L
1
2
L
2
U
2
L
2
L
L
R
R
1
R
1
D
1
L
1
L
L
1
U

Story

AtCoder Inc. has decided to move to a new office. To keep costs down, instead of hiring a moving company, CEO Takahashi will do the moving himself.

The old office is filled with a large number of cardboard boxes laid out on the floor, and all of them must be transported to the entrance. Boxes can be stacked and carried multiple at once, but if stacked too heavily, they may collapse under their own weight.

Your task is to find a way to safely carry all the boxes to the entrance using as few moves as possible.

Problem Statement

There is an office consisting of N \times N squares. Let (0, 0) be the coordinates of the top-left square, and (i, j) be the coordinates of the square located i squares down and j squares to the right from there. The office entrance is located at square (0, 0).

Initially, one cardboard box is placed in every square except the entrance. Each cardboard box has two numerical values: weight and durability. The box at square (i, j) has a weight of w_{i,j} and a durability of d_{i,j}.

Cardboard boxes can be stacked vertically to carry multiple boxes at once. Starting from the initial position (0,0), Takahashi’s goal is to carry all the boxes out of the office by repeatedly performing the following operations:

  1. Pick up the cardboard box at the current position. If already holding boxes, place the new one on top. This operation cannot be performed if there is no box at the current position.
  2. Place the topmost box in hand at the current position. This cannot be performed if there is already a box in that square.
  3. Move to an adjacent square in one of the four directions: up, down, left, or right. It is allowed to move onto squares that have a box, but moving outside the N \times N area is not allowed.

Takahashi is very strong and can carry any number of boxes regardless of total weight. However, the durability of boxes he is holding decreases when he moves (operation 3). A box with durability reduced to 0 or below will be crushed and judged as WA.

The amount by which a box’s durability decreases is equal to the total weight of all boxes stacked above it. Specifically, if the boxes currently held have weights w_1, w_2, \ldots, w_n from bottom to top, then the i-th box from the bottom (1 \le i \le n) will lose \sum_{j=i+1}^n w_j durability per move.

Durability decreases only during movement (operation 3). It does not change during picking up or placing a box (operations 1 and 2). Durability also does not recover after placing a box on the floor.

When moving to the entrance at (0, 0) using operation 3, all boxes currently held are carried out of the office.

You may perform at most 2 \times N^3 operations in total. Your task is to carry out all the cardboard boxes using as few moves as possible.

Scoring

Let T be the number of times operation 3 (movement) is performed, and let R be the number of cardboard boxes remaining in the office. The score is calculated as follows:

  • If R > 0: N^2 - R
  • If R = 0: N^2 + 2 \times N^3 - T

Here, T counts only the number of times operation 3 (movement) is performed; operations 1 (pick up) and 2 (place) are not included in T. However, the limit on the total number of operations (at most 2 \times N^3) applies to all operations.

There are 150 test cases, and the score of a submission is the total score for each test case. If your submission produces an illegal output or exceeds the time limit for some test cases, the submission itself will be judged as WA or TLE , and the score of the submission will be zero. The highest score obtained during the contest will determine the final ranking, and there will be no system test after the contest. If more than one participant gets the same score, they will be ranked in the same place regardless of the submission time.

Input

Input is given from Standard Input in the following format:

N
w_{0,0} \cdots w_{0,N-1}
\vdots
w_{N-1,0} \cdots w_{N-1,N-1}
d_{0,0} \cdots d_{0,N-1}
\vdots
d_{N-1,0} \cdots d_{N-1,N-1}
  • In all test cases, N is fixed at 20.
  • w_{i,j} is an integer representing the weight of the cardboard box placed at square (i, j). Since there is no box at square (0,0), we have w_{0,0} = 0. For all other squares, 1 \leq w_{i,j} \leq 10^3.
  • d_{i,j} is an integer representing the durability of the cardboard box placed at square (i, j). At square (0,0), d_{0,0} = 0. For all other squares, 10 \leq d_{i,j} \leq 3\times 10^4.

Output

Let the operation performed in turn t be represented by a single character a_t as follows:

  1. If performing operation 1: 1
  2. If performing operation 2: 2
  3. If performing operation 3:
      Up: U
      Down: D
      Left: L
      Right: R

Let L be the number of operations. Then, output to Standard Output in the following format:

a_0
\vdots
a_{L-1}

Show example

Input Generation

  • \mathrm{rand\_double}(L,U): Generates a uniformly random real number between L and U.

Generation of w

For every square (i, j) except (0, 0), we generate w_{i,j} as \mathrm{round}(\mathrm{rand\_double}(1, \sqrt{1000})^2).

Generation of d

For every square (i, j) except (0, 0), we generate d_{i,j} as \mathrm{round}(w_{i,j} \times \mathrm{rand\_double}(10, 30)).

Tools (Input generator and visualizer)

Please be aware that sharing visualization results or discussing solutions/ideas during the contest is prohibited.

Sample Input 1

20
0 3 749 809 20 263 83 30 559 8 5 269 675 47 235 204 747 216 134 244
2 651 130 557 93 426 690 873 506 98 22 251 213 814 874 79 857 6 158 639
2 965 45 107 259 20 957 244 18 962 152 82 327 226 24 131 99 1 255 60
177 1 42 878 353 185 89 656 757 54 351 349 489 249 679 756 191 395 719 145
613 203 741 455 1 402 877 791 146 956 506 262 280 746 156 733 66 237 389 115
164 738 84 747 10 579 81 6 78 215 337 556 479 498 2 674 120 737 429 106
872 394 35 325 49 6 129 185 45 218 18 892 162 7 419 579 768 11 724 266
29 236 832 372 132 857 840 10 446 74 734 199 148 802 24 467 321 410 237 50
715 391 412 13 312 2 138 645 333 260 621 736 483 876 62 9 44 77 180 3
165 852 738 29 110 119 857 974 104 103 886 500 271 819 155 467 579 108 466 837
243 39 711 197 494 17 800 721 15 193 138 5 451 736 311 272 582 177 112 533
441 65 2 544 545 259 147 10 101 411 23 144 449 18 668 211 497 475 470 867
179 661 8 73 600 371 374 417 150 629 520 236 625 508 168 733 36 282 427 121
534 715 558 187 707 714 368 882 437 607 27 18 15 988 306 198 130 343 70 42
248 257 714 3 133 859 658 52 385 487 572 25 211 485 381 453 198 496 576 7
18 89 103 218 494 679 981 133 59 69 73 397 517 567 542 8 619 13 247 373
355 745 81 291 401 142 357 244 7 581 440 6 963 173 750 763 1 382 278 5
275 103 7 843 2 14 86 374 97 218 15 319 55 503 886 44 27 228 375 796
430 146 873 39 5 714 366 732 679 369 642 344 978 237 230 98 273 98 58 850
266 608 739 2 190 592 194 84 611 14 101 909 4 582 122 12 122 994 635 916
0 89 10274 11922 300 6685 978 640 13718 132 143 7028 18239 1327 6881 2284 21156 2760 1998 5070
57 17805 2901 14519 1693 10841 11743 18976 9379 2092 285 3524 5983 16567 22972 1063 19938 131 4309 15177
40 21359 1207 2121 3421 233 27186 6872 310 11251 3786 1176 5352 4669 644 2427 1063 16 5886 1000
3615 18 918 12387 7059 4315 2057 15533 15664 1195 10141 8595 5218 6993 10755 19254 2432 9972 20357 3718
8450 3919 8454 5988 19 10140 12007 18903 3935 18739 11371 4330 3194 11908 1710 15085 1585 6893 5701 1207
2641 20082 1007 20670 242 16408 821 174 1941 6053 5509 10545 11073 13932 58 9389 3431 10249 5398 2521
19054 4835 829 4674 1201 126 2364 3885 858 5383 501 21304 4520 180 5604 9931 21101 168 19471 5338
712 5765 11653 9607 2457 18495 9954 105 11699 818 16356 3906 1654 10149 438 13133 7833 4447 5445 1326
10666 6309 4688 285 5169 40 1404 18295 3541 7125 8287 20290 8837 17858 1621 135 1115 1091 3288 54
2597 9955 16763 471 2335 1574 14642 16187 2376 1887 24636 5641 7433 17306 2957 6663 5966 3044 5358 9769
5905 611 17099 3300 11161 385 15895 19522 435 2108 3650 141 8058 21485 3988 2737 16273 4105 2571 11724
7296 1489 51 6519 5911 3647 2533 236 1190 4266 500 3338 7312 385 19463 4942 10835 11174 10700 9738
4477 16314 165 805 17700 4016 7057 12420 2756 17887 6796 5143 12927 6174 4740 20452 424 3101 11615 2445
13368 15983 15135 5582 12578 15525 4649 24252 6902 17168 460 228 413 23337 8237 3631 3838 6815 1706 1166
6713 5548 10910 65 1426 17897 8171 886 5466 8932 7274 277 2969 12341 10707 10334 2143 12639 7016 144
462 1829 1530 6394 14306 7206 16721 3469 1058 1201 1641 7989 7068 8612 8485 197 8113 306 6585 6213
4014 13889 2016 7397 6739 3985 10474 2701 107 8285 5588 90 10340 2717 16467 20426 22 9518 5965 124
6569 2065 136 23365 25 276 992 8245 1736 4797 316 6097 712 9186 25794 1282 431 3350 8782 9615
9031 3928 13928 394 118 18798 6870 18849 8115 10434 8884 3992 29004 6921 3450 2052 5705 2732 837 18597
6226 15329 13644 58 3923 10666 4191 1802 18180 242 2764 13987 101 10450 1509 311 1638 19358 11533 16943

Sample Output 1

D
R
1
R
R
1
U
1
L
1
L
1
L
R
R
R
R
R
R
R
R
1
D
1
L
1
L
1
L
1
L
1
2
L
2
U
2
L
2
L
L
R
R
1
R
1
D
1
L
1
L
L
1
U