A - Walking on Tiles Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

問題文

50\times 50 マスの広さの床に長方形のタイルが隙間なく敷き詰められている。 各タイルは 1\times 1, 1\times 2, 2\times 1 のいずれかの大きさである。 一番左上のマスの座標を (0,0) とし、そこから下方向に i マス、右方向に j マス進んだ先のマスの座標を (i, j) とする。 高橋くんは (si, sj) のマスからスタートして、以下の条件を満たす経路で移動することが出来る。

  • 位置 (i, j) のマスに居る状態から、一歩で位置 (i-1,j), (i+1,j), (i,j-1), (i,j+1) のいずれかのマスに移動できる。
  • 同じタイルは高々1回までしか踏んではならない。初期位置にあるタイルは既に踏まれているものとする。

各マスには整数値が書かれており、訪れたマス(初期位置のマスを含む)に書かれた数値の合計が経路の得点となる。 出来るだけ高い得点の得られる移動経路を求めよ。

例

上の3つの図のうち、左の図のみが条件を満たす移動経路である。真ん中の図では同じタイルを連続して二度踏んでいる。右の図では一度タイルから離れた後に戻ってきて二度目を踏んでいる。

サンプル出力のビジュアライズ結果。 赤丸は初期位置を、緑丸は最終位置を表している。 踏まれたタイルは水色で表されている。

得点

出力された経路の得点がそのままテストケースの得点となる。 条件を満たさない出力がされた場合はWAと判定される。 テストケースは全部で100個あり、各テストケースの得点の合計が提出の得点となる。 1つ以上のテストケースでAC以外の判定がされた場合、提出の得点は0点となる。 コンテスト時間中に得た最高得点で最終順位が決定され、コンテスト終了後のシステムテストは行われない。 同じ得点を複数の参加者が得た場合、その得点を獲得した提出の早い方が上位となる。

入力

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

si sj
t_{0,0} t_{0,1} \ldots t_{0,49}
\vdots
t_{49,0} t_{49,1} \ldots t_{49,49}
p_{0,0} p_{0,1} \ldots p_{0,49}
\vdots
p_{49,0} p_{49,1} \ldots p_{49,49}
  • (si,sj)は初期位置を表し、0\leq si,sj\leq 49 を満たす。
  • t_{i,j} はマス (i,j) の上に置かれているタイルを表す整数値である。t_{i,j} の値が同じマスの上には同じタイルが置かれている。タイルの総数をMとすると、0\leq t_{i,j}\leq M-1を満たす。
  • p_{i,j} はマス (i,j) を訪れたときに得られる得点を表す整数値であり、0\leq p_{i,j}\leq 99 を満たす。

出力

(i, j) から (i-1,j), (i+1,j), (i,j-1), (i,j+1) のマスへの移動をそれぞれ U, D, L, R として、移動経路を文字列で表し、1行で出力せよ。

入力生成方法

si,sj の生成

0 以上 49 以下の整数を一様ランダムに生成する。

t_{i,j} の生成

全てのマスの上に 1\times1 の大きさのタイルが置かれた状態からスタートする。 50\times 50 個のマスをランダムな順にシャッフルし、各マスについて以下の処理を順に行う。

  • 現在のマスの上に置かれているタイルが 1\times 1 の場合、隣接するマスのうちで上に置かれているタイルが 1\times 1 であるものをランダムに一つ選び、2つのタイルを一つに繋げる。そのような隣接マスが一つも存在しない場合は何もしない。
  • 現在のマスの上に置かれているタイルが 1\times 1 でない場合、何もしない。

p_{i,j} の生成

各マスについて独立に、0 以上 99 以下の整数を一様ランダムに生成する。

ツール

入力例 1

1 49
0 1 2 2 3 3 4 5 6 7 8 8 9 9 10 10 11 11 12 12 13 13 14 15 16 16 17 18 19 19 20 21 22 23 23 24 25 26 27 27 28 28 29 29 30 31 31 32 33 34
0 1 35 35 36 37 37 5 6 7 38 39 39 40 41 42 43 43 44 44 45 45 14 46 47 47 17 18 48 49 20 21 22 50 51 24 25 52 53 54 54 55 56 57 30 58 59 59 33 34
60 61 62 63 36 64 65 65 66 67 67 68 69 69 41 42 70 71 71 72 73 74 74 46 75 75 76 76 48 77 77 78 79 50 51 80 80 52 53 81 81 82 56 83 83 58 84 85 86 86
60 61 62 63 87 64 88 89 66 90 91 68 92 93 94 94 95 95 96 96 73 97 97 98 99 99 100 101 102 103 103 78 79 104 104 105 106 106 107 108 108 82 109 109 110 110 84 85 111 111
112 113 114 115 87 116 88 117 117 90 91 118 118 93 119 120 121 122 123 124 124 125 125 98 126 127 100 101 102 128 128 129 129 130 130 105 131 132 132 133 134 135 135 136 137 138 139 140 141 141
112 113 114 115 142 116 143 144 144 145 146 147 148 148 119 149 121 122 123 150 150 151 151 152 126 153 154 155 155 156 157 157 158 158 159 159 160 161 161 162 134 163 163 164 137 138 139 165 165 166
167 168 169 170 170 171 143 172 172 145 146 173 174 175 176 149 177 177 178 179 179 180 180 152 181 153 154 182 182 156 183 183 184 184 185 185 160 186 186 162 187 188 189 164 190 191 192 193 194 166
195 168 196 196 197 171 198 199 199 200 201 173 174 175 176 202 203 203 204 204 205 206 207 208 208 209 210 210 211 211 212 212 213 213 214 215 216 216 217 218 218 188 189 219 190 191 192 193 194 220
195 221 222 223 224 224 198 225 226 200 201 227 228 228 229 230 231 231 232 233 233 206 234 235 236 209 237 238 238 239 240 241 242 242 214 215 243 243 244 244 245 246 246 219 247 247 248 248 249 220
250 250 222 251 251 252 253 253 226 254 255 227 256 256 229 230 257 257 258 259 259 260 234 235 236 261 262 263 264 239 265 241 266 267 268 269 270 271 272 272 245 273 274 274 275 275 276 276 277 277
278 279 279 280 280 252 281 281 282 254 255 283 283 284 285 286 286 287 258 288 288 289 290 291 291 261 262 263 292 293 265 294 266 267 268 295 270 271 296 297 297 298 298 299 300 301 301 302 303 303
304 304 305 306 307 308 309 309 282 310 310 311 311 284 312 312 313 314 314 315 315 289 290 316 317 318 319 319 292 293 320 321 321 322 323 295 324 324 296 325 325 326 326 299 300 327 327 328 328 329
330 331 331 306 307 308 332 332 333 333 334 334 335 336 337 338 313 339 339 340 341 342 342 316 317 318 343 343 344 344 320 345 346 322 323 347 348 349 349 350 351 352 353 354 355 355 356 356 357 357
330 358 359 360 360 361 361 362 363 363 364 364 335 365 337 338 366 367 368 368 341 369 370 370 371 371 372 372 373 374 374 345 346 375 376 347 348 377 378 379 351 352 353 354 380 380 381 382 383 384
385 386 359 387 387 388 389 362 390 390 391 392 392 365 393 393 366 367 394 394 395 396 396 397 397 398 399 400 373 401 401 402 403 375 376 404 404 377 378 379 405 405 406 407 407 408 381 409 383 384
385 386 410 411 412 388 389 413 414 414 391 415 416 417 418 419 419 420 420 421 422 422 423 424 425 425 399 426 426 427 427 402 403 428 429 429 430 430 431 432 432 433 406 434 434 435 435 409 436 437
438 438 439 411 440 440 441 442 443 443 444 445 416 417 446 446 447 448 448 421 449 450 451 424 452 452 453 453 454 455 456 457 457 428 458 458 459 460 461 462 463 463 464 465 465 466 467 467 436 437
468 469 439 470 471 472 473 442 474 475 475 445 476 477 478 478 447 479 479 480 449 450 451 481 482 482 483 483 454 455 456 484 485 486 487 487 459 460 461 488 489 490 464 491 492 492 493 493 494 495
468 496 497 497 471 472 473 498 474 499 500 500 476 477 501 501 502 503 504 480 505 505 506 481 507 508 508 509 510 511 511 484 485 486 512 513 513 514 514 488 489 490 515 491 516 517 517 518 519 495
520 496 521 522 522 523 524 525 526 527 528 529 530 531 531 532 533 503 504 534 535 535 536 537 507 538 538 509 539 539 540 540 541 542 542 543 544 544 545 546 546 547 548 548 516 549 549 518 519 550
520 551 521 552 553 554 524 525 526 527 528 529 555 556 556 532 533 557 558 534 559 559 536 560 561 562 562 563 564 565 566 566 567 568 568 569 570 571 572 573 574 547 575 576 577 577 578 578 579 579
580 551 581 552 553 554 582 582 583 584 584 585 555 586 586 587 587 557 558 588 588 589 590 560 591 592 593 563 564 594 594 595 567 596 596 569 570 597 572 573 574 598 598 576 599 600 600 601 602 603
580 604 604 605 606 607 608 609 583 610 610 611 612 613 614 614 615 616 616 617 618 618 590 619 591 620 593 621 622 623 623 595 624 625 625 626 627 597 628 628 629 629 630 630 599 631 631 601 602 603
632 632 633 605 606 634 608 609 635 635 636 611 612 613 637 637 615 638 638 617 639 640 640 619 641 620 642 621 622 643 643 644 624 645 645 626 627 646 647 648 649 649 650 650 651 651 652 653 653 654
655 655 633 656 656 634 657 657 658 659 636 660 660 661 661 662 662 663 663 664 639 665 665 666 641 667 642 668 668 669 669 644 670 671 672 673 673 674 647 648 675 675 676 677 677 678 678 679 680 654
681 682 682 683 684 684 685 685 658 686 686 687 688 688 689 690 691 692 692 664 693 693 694 694 695 667 696 696 697 697 698 698 670 671 672 699 700 674 701 701 702 703 703 704 704 705 705 679 706 707
708 709 710 683 711 712 712 713 714 715 716 717 717 718 719 690 691 720 720 721 721 722 722 723 695 724 725 725 726 726 727 728 729 729 730 730 700 731 732 732 702 733 734 735 736 736 737 738 706 707
708 709 710 739 739 740 741 713 714 715 716 742 742 743 719 744 744 745 746 747 748 749 750 751 752 753 753 754 754 755 755 728 756 756 757 758 759 759 760 761 761 733 734 735 762 763 737 738 764 764
765 766 766 767 768 740 769 770 771 772 773 774 774 743 775 775 776 745 746 747 748 749 750 751 752 777 777 778 778 779 779 780 780 781 757 758 782 782 783 784 785 786 786 787 787 763 788 788 789 789
765 790 791 767 768 792 769 770 771 772 793 794 795 795 796 796 797 797 798 799 799 800 800 801 802 802 803 803 804 804 805 805 806 806 807 808 808 809 783 784 810 811 812 812 813 814 815 816 816 817
818 818 791 819 819 792 820 821 821 822 793 794 823 824 824 825 826 826 798 827 828 828 829 801 830 831 831 832 832 833 834 835 835 836 836 837 837 809 838 838 810 811 839 840 813 814 815 841 842 842
843 844 845 845 846 846 820 847 848 822 849 849 823 850 851 825 852 852 853 853 854 855 829 856 857 858 858 859 859 833 860 860 861 861 862 862 863 863 864 864 865 866 839 840 867 868 869 841 870 870
843 844 871 871 872 873 874 847 848 875 876 876 877 850 878 879 880 881 882 883 854 884 884 856 857 885 886 886 887 887 888 889 890 890 891 891 892 893 894 895 865 866 896 896 867 868 869 897 897 898
899 900 900 901 902 873 903 903 904 905 906 906 877 907 878 879 880 881 882 883 908 909 909 910 910 885 911 911 912 912 888 889 913 914 915 916 892 917 894 918 918 919 920 920 921 921 922 923 923 898
899 924 924 901 902 925 926 927 927 905 928 929 930 930 931 931 932 933 933 934 935 935 936 937 937 938 938 939 940 941 941 942 942 914 915 916 943 917 944 945 945 919 946 947 947 948 948 949 950 950
951 951 952 953 954 925 926 955 956 956 928 957 958 959 959 960 961 962 963 963 964 964 965 966 967 968 969 970 940 971 972 973 973 974 974 975 976 977 978 979 979 980 946 981 981 982 982 949 983 983
984 985 952 953 954 986 987 955 988 989 990 957 991 991 992 992 961 993 994 995 995 996 965 966 967 968 969 970 997 971 972 998 999 999 1000 1001 976 977 978 1002 1002 980 1003 1003 1004 1005 1006 1006 1007 1008
984 1009 1009 1010 1011 986 987 1012 1012 989 990 1013 1013 1014 1015 1016 1017 993 994 1018 1019 996 1020 1020 1021 1022 1022 1023 1023 1024 1025 998 1026 1027 1000 1001 1028 1029 1030 1030 1031 1032 1032 1033 1004 1005 1034 1035 1007 1036
1037 1037 1038 1010 1011 1039 1039 1040 1040 1041 1042 1043 1043 1014 1015 1016 1017 1044 1044 1018 1045 1046 1047 1047 1021 1048 1049 1050 1050 1051 1025 1052 1052 1027 1053 1054 1054 1029 1055 1055 1031 1056 1056 1033 1057 1057 1034 1058 1058 1036
1059 1060 1060 1061 1061 1062 1062 1063 1064 1041 1042 1065 1066 1067 1068 1068 1069 1070 1070 1071 1045 1046 1072 1072 1073 1048 1049 1074 1075 1051 1076 1077 1077 1078 1079 1079 1080 1081 1082 1082 1083 1084 1084 1085 1085 1086 1087 1088 1089 1090
1059 1091 1092 1093 1094 1095 1095 1063 1096 1097 1097 1065 1066 1098 1098 1099 1100 1100 1101 1102 1102 1103 1104 1105 1106 1106 1107 1107 1075 1108 1109 1109 1110 1078 1111 1112 1080 1113 1114 1115 1083 1116 1117 1118 1119 1120 1087 1088 1089 1090
1121 1091 1092 1093 1122 1122 1123 1123 1096 1124 1125 1126 1127 1127 1128 1099 1129 1129 1130 1130 1131 1132 1104 1105 1133 1133 1134 1134 1135 1135 1136 1136 1137 1137 1111 1112 1138 1113 1114 1115 1139 1116 1117 1118 1119 1120 1140 1140 1141 1142
1121 1143 1143 1144 1144 1145 1145 1146 1146 1124 1125 1126 1147 1147 1148 1148 1149 1150 1151 1152 1131 1132 1153 1154 1155 1155 1156 1157 1158 1159 1160 1160 1161 1161 1162 1163 1164 1165 1166 1166 1139 1167 1168 1169 1170 1170 1171 1171 1141 1142
1172 1173 1174 1175 1176 1177 1178 1178 1179 1180 1181 1181 1182 1183 1184 1185 1149 1150 1186 1152 1187 1187 1153 1154 1188 1188 1156 1157 1189 1159 1190 1191 1191 1192 1162 1193 1164 1165 1194 1195 1195 1167 1168 1169 1196 1196 1197 1197 1198 1198
1172 1173 1174 1175 1176 1199 1199 1200 1179 1180 1201 1201 1182 1202 1184 1185 1203 1203 1186 1204 1204 1205 1206 1207 1208 1208 1209 1210 1189 1211 1190 1212 1213 1192 1214 1193 1215 1216 1216 1217 1218 1218 1219 1220 1220 1221 1221 1222 1222 1223
1224 1225 1225 1226 1226 1227 1227 1228 1229 1229 1230 1231 1231 1202 1232 1233 1233 1234 1234 1235 1236 1237 1206 1238 1238 1239 1239 1210 1240 1240 1241 1212 1242 1243 1243 1244 1215 1245 1246 1247 1248 1249 1219 1250 1251 1251 1252 1253 1253 1223
1224 1254 1254 1255 1256 1256 1257 1228 1258 1258 1230 1259 1259 1260 1261 1262 1263 1264 1265 1235 1266 1237 1267 1268 1269 1270 1270 1271 1272 1273 1274 1275 1242 1276 1277 1244 1278 1245 1246 1247 1248 1279 1279 1280 1280 1281 1252 1282 1283 1284
1285 1286 1286 1255 1287 1288 1289 1289 1290 1291 1291 1292 1292 1260 1261 1262 1263 1264 1265 1293 1266 1294 1295 1268 1269 1296 1296 1297 1272 1273 1274 1298 1298 1276 1277 1299 1300 1300 1301 1301 1302 1302 1303 1303 1304 1281 1305 1282 1283 1284
1285 1306 1306 1307 1308 1288 1309 1309 1310 1310 1311 1311 1312 1313 1313 1314 1315 1315 1316 1293 1317 1318 1295 1319 1319 1320 1321 1297 1322 1322 1323 1324 1324 1325 1325 1299 1326 1327 1328 1329 1330 1331 1332 1332 1304 1333 1334 1335 1336 1337
1338 1338 1339 1307 1308 1340 1340 1341 1342 1342 1343 1343 1312 1344 1344 1345 1345 1346 1316 1347 1317 1318 1348 1348 1349 1320 1321 1350 1351 1351 1323 1352 1352 1353 1354 1354 1326 1327 1328 1329 1330 1331 1355 1355 1356 1356 1334 1335 1336 1337
50 22 28 77 64 20 0 38 74 88 84 50 15 38 97 45 37 2 24 37 90 97 44 67 65 38 11 76 21 62 23 83 7 33 47 64 90 25 11 40 20 71 48 14 78 2 61 84 62 58
54 31 65 33 17 71 22 54 66 28 40 18 19 25 13 53 22 70 62 80 27 28 30 97 69 32 79 76 13 25 98 86 48 6 92 67 13 28 11 7 55 67 86 18 4 61 15 15 32 11
60 34 56 43 0 39 66 0 75 89 52 71 93 40 53 13 63 46 34 58 1 89 75 32 75 95 27 61 88 79 74 71 37 39 67 6 72 13 85 33 83 9 61 96 18 35 20 5 90 30
97 72 96 6 71 9 25 66 44 95 60 5 5 7 10 51 39 75 41 19 6 71 34 76 10 71 32 78 32 75 32 34 9 25 2 62 53 47 68 34 89 15 29 85 0 59 75 14 90 28
32 45 33 78 53 12 88 81 26 22 33 82 10 63 46 56 96 47 44 47 45 81 66 50 84 87 4 40 46 2 95 63 90 83 4 8 37 89 73 47 79 97 4 99 34 25 37 22 29 19
90 19 97 46 41 81 13 11 80 54 88 79 76 37 86 0 89 39 41 79 33 57 18 10 22 58 65 53 46 20 22 90 13 82 77 6 28 42 73 21 55 69 34 48 23 32 98 79 41 17
90 47 92 61 8 18 2 79 30 48 17 56 81 84 1 51 31 23 71 90 38 91 76 51 29 19 32 50 92 55 89 77 23 40 0 87 4 52 38 55 89 61 87 40 32 21 98 42 71 23
39 72 50 44 10 78 66 55 58 91 67 63 66 39 15 52 38 67 95 79 47 41 87 46 9 61 65 6 0 17 74 49 99 80 35 36 67 4 59 46 70 3 95 61 39 5 51 22 82 10
71 93 13 69 73 60 68 40 84 19 53 12 64 91 79 66 3 42 13 93 78 72 26 46 50 5 38 41 42 27 47 35 2 75 99 16 77 25 67 70 66 40 2 48 8 60 46 34 45 78
59 77 22 49 20 73 64 58 44 19 73 8 13 48 15 72 5 82 22 57 88 63 59 36 33 21 80 64 40 28 60 71 63 89 67 10 8 43 10 18 31 28 10 19 25 40 56 84 15 1
5 7 63 62 47 32 7 29 41 51 21 73 21 43 99 65 22 7 97 49 86 5 13 51 56 62 12 23 34 93 36 3 52 55 49 45 1 40 26 96 51 1 73 45 36 33 1 74 86 32
63 54 29 70 87 98 69 19 31 88 11 87 5 31 24 17 26 36 9 41 6 59 11 54 49 84 34 43 66 43 20 12 75 68 24 4 20 24 9 47 64 5 2 45 75 42 90 32 83 85
73 87 73 10 91 44 92 61 90 51 57 66 94 58 15 20 68 51 69 13 41 43 33 85 1 21 30 50 8 82 47 10 79 83 86 98 85 5 8 68 92 84 78 64 40 47 12 64 46 32
26 21 88 56 79 90 87 86 86 46 91 93 50 50 72 48 62 57 32 74 49 23 66 9 7 73 17 35 52 51 29 80 64 64 76 22 63 86 55 99 17 92 87 20 40 44 79 51 55 78
69 24 52 79 6 76 31 3 14 22 16 5 45 77 11 80 52 73 95 71 88 51 78 32 21 78 78 7 67 20 27 7 11 33 15 78 43 35 64 68 36 81 87 74 33 18 74 7 87 4
67 16 66 23 84 66 30 36 87 93 60 47 22 19 1 97 67 43 70 29 82 15 73 16 76 96 9 95 31 45 36 46 47 68 90 56 77 70 49 78 40 36 17 90 55 66 58 20 43 46
27 2 1 27 57 23 54 93 87 24 88 41 55 3 22 54 72 69 41 43 45 58 95 65 92 9 66 49 16 96 8 56 82 34 1 43 4 77 15 63 88 86 73 95 53 52 90 86 94 49
42 38 70 49 40 6 67 34 40 60 21 54 0 47 2 2 1 79 8 41 45 32 62 92 82 49 9 87 63 15 11 51 12 32 3 25 39 34 12 33 34 57 73 97 69 64 80 68 28 77
12 93 99 20 9 33 76 73 82 40 31 10 70 6 0 83 90 0 93 69 23 94 91 50 28 39 93 26 70 72 32 28 14 55 96 24 38 33 79 50 79 91 62 27 90 24 94 5 15 4
89 8 31 0 0 60 47 37 96 9 84 0 39 4 64 40 74 58 25 61 71 47 49 50 44 46 82 65 38 65 99 14 27 24 45 45 17 55 21 37 35 38 62 87 13 21 27 93 55 76
0 36 73 89 13 98 19 18 97 92 74 22 0 74 6 22 35 6 2 73 80 36 1 65 54 82 98 65 40 11 86 70 80 52 85 3 36 31 73 29 71 12 27 70 78 5 41 71 86 77
57 80 18 3 78 32 52 14 88 17 92 49 55 58 95 49 56 2 65 7 56 42 51 98 69 26 69 18 95 84 71 48 32 23 70 68 58 46 25 57 29 10 4 66 31 14 38 15 61 34
69 58 40 38 98 37 39 25 84 4 87 9 95 37 9 63 5 81 71 74 50 86 44 10 33 66 25 44 94 7 81 70 25 62 65 94 11 15 98 23 41 71 45 82 6 43 78 78 58 93
56 69 38 53 13 28 58 46 8 97 18 39 84 57 9 68 38 8 23 66 41 27 98 45 77 64 83 17 67 30 15 39 36 84 50 21 22 54 42 98 86 1 95 97 66 98 53 34 17 91
44 50 17 76 79 52 91 68 21 24 30 51 57 81 74 88 70 46 85 2 29 16 13 39 54 10 62 67 83 50 7 73 44 42 10 51 25 39 53 51 49 12 13 78 53 73 31 6 64 20
45 88 62 61 41 77 8 33 22 81 44 75 1 24 2 22 20 63 50 7 48 55 16 8 59 88 87 13 75 79 78 89 74 97 39 85 42 99 24 14 14 18 11 51 48 3 61 94 30 50
82 83 15 71 63 1 5 99 39 70 15 72 85 28 64 64 50 7 61 82 95 78 20 18 16 41 16 56 21 1 53 37 74 16 47 49 6 36 17 16 40 1 90 69 77 97 58 64 94 54
4 4 63 94 85 76 46 72 78 26 2 11 1 21 82 65 71 3 37 22 87 3 59 52 52 20 75 83 68 59 48 99 77 65 14 41 96 71 81 72 28 16 10 0 58 25 12 43 48 13
20 91 6 64 82 82 60 39 50 42 56 75 13 92 44 76 53 69 93 6 80 82 25 39 39 9 10 85 32 48 1 7 96 92 75 6 83 66 61 50 78 61 71 82 82 80 7 52 68 21
78 43 31 32 81 86 47 75 20 20 75 46 95 54 44 74 34 88 56 69 53 66 65 43 8 38 76 71 65 77 81 83 50 75 42 83 87 82 85 83 26 8 60 74 65 72 31 38 32 44
59 22 25 85 23 7 73 25 4 43 63 45 57 71 91 90 94 80 46 39 26 44 4 12 81 73 4 76 5 44 23 94 6 28 22 65 81 26 27 33 90 72 86 82 43 35 90 8 91 65
70 39 90 65 83 36 62 44 33 58 16 2 75 4 90 48 13 62 26 15 82 87 76 41 96 97 89 12 29 28 68 59 80 52 70 2 47 68 47 66 64 27 12 61 53 95 11 91 27 21
94 46 29 29 93 22 11 82 44 47 53 73 0 72 85 7 91 66 36 65 66 72 1 10 63 74 24 75 26 75 56 61 87 53 40 29 2 54 2 64 18 22 8 81 86 40 78 42 19 27
23 96 2 50 52 30 86 70 98 52 61 47 6 47 75 15 24 70 38 41 77 18 79 85 46 65 57 11 57 4 7 34 8 25 81 48 69 94 27 71 13 58 78 28 10 35 32 5 58 35
80 96 65 43 84 78 3 3 16 28 47 85 11 74 66 47 70 63 37 78 91 40 63 29 22 59 47 46 87 15 20 95 1 79 7 16 94 76 4 84 31 1 47 33 85 52 98 59 7 75
88 59 64 16 74 81 4 58 14 65 85 28 76 59 9 53 10 39 25 98 46 7 75 58 73 46 4 43 40 50 9 40 19 7 56 5 55 22 55 89 75 32 19 30 23 17 99 28 57 24
1 80 29 51 34 87 99 28 80 17 67 60 5 46 68 92 31 79 46 18 39 39 16 20 96 58 91 25 3 1 47 53 30 2 69 49 0 18 9 82 16 68 51 54 43 18 37 82 55 11
18 76 63 42 9 13 48 23 50 4 11 28 32 16 7 2 9 46 53 93 25 86 63 55 82 81 15 71 39 97 93 63 96 48 71 79 39 32 29 60 14 55 57 18 77 32 4 57 83 74
91 83 23 16 51 25 60 54 50 49 10 67 65 78 17 79 88 2 40 76 80 77 31 16 82 62 34 60 15 45 22 35 34 87 45 27 25 9 61 78 17 17 19 76 94 58 47 47 63 37
76 98 70 13 45 49 76 4 29 45 11 3 56 36 58 4 93 80 60 60 48 13 66 87 20 85 2 12 54 1 7 59 61 33 95 69 73 63 13 9 13 68 14 99 56 17 88 48 71 40
52 61 71 60 66 91 49 73 17 33 15 7 65 66 62 79 70 50 7 25 8 29 3 93 4 4 13 71 27 0 23 91 57 70 51 50 79 92 22 35 87 30 3 52 4 5 94 28 35 45
82 35 3 85 21 10 56 32 84 7 31 34 16 78 34 79 23 9 84 78 75 64 64 51 48 19 11 98 87 94 75 55 5 3 10 2 73 57 75 50 21 47 70 64 97 96 47 66 91 34
78 46 96 45 78 31 78 9 16 52 14 42 98 23 80 99 69 60 83 51 45 64 27 75 65 23 26 63 17 4 70 71 21 38 94 27 48 65 58 78 72 45 49 27 43 14 76 3 28 65
47 83 28 63 1 28 83 82 18 92 91 87 53 76 77 82 7 1 37 92 91 63 44 24 0 12 24 74 13 73 84 81 53 5 85 9 62 84 73 71 85 0 7 64 30 49 95 62 80 15
16 74 78 31 47 55 33 38 70 33 34 12 50 57 49 14 4 22 79 35 74 18 58 63 58 40 18 69 81 79 46 33 3 81 25 89 26 42 49 10 52 58 8 48 30 9 47 19 94 22
31 38 59 13 55 81 2 33 81 61 20 7 36 63 61 65 62 68 5 12 58 80 8 8 30 14 30 50 6 24 77 65 11 1 64 67 45 39 19 26 45 60 93 77 2 24 34 14 60 50
40 36 77 19 56 97 42 38 30 71 68 82 70 42 37 56 71 22 78 52 43 0 87 30 64 18 47 55 10 25 48 83 95 57 65 89 63 69 59 88 74 20 57 75 19 21 65 4 93 93
77 35 97 44 2 93 82 76 96 84 14 70 98 41 58 82 67 74 15 1 77 84 52 10 22 58 65 99 16 35 14 34 65 3 92 32 43 29 56 73 97 30 66 86 56 99 82 45 83 97
73 88 13 17 24 43 70 18 65 61 46 21 8 68 82 64 81 87 1 33 8 56 54 84 8 66 92 40 89 80 22 41 50 10 0 25 97 13 40 0 80 95 60 4 60 51 2 0 51 68
49 69 41 45 58 41 33 92 20 45 23 57 43 44 30 83 37 75 0 46 27 90 23 45 3 75 42 19 74 61 26 49 52 80 36 93 98 70 15 52 10 26 95 32 1 47 97 8 79 69

出力例 1

LDDDDDLLULLLUUULLLDDRDDLDDLDDDDDLLLDDLDDRDRDDRRRUURRURUUULULDDD

Problem Statement

There is a floor consisting of 50\times 50 squares. The floor is covered with rectangular tiles without any gaps. Each tile has a size of either 1\times 1, 1\times 2, or 2\times 1 squares. Let (0, 0) denote the top-left square, and (i, j) denote the square at the i-th row from the top and j-th column from the left. Takahashi starts from (si, sj) and walks along a path satisfying the following conditions.

  • From (i, j), he can move to (i-1,j), (i+1,j), (i,j-1), or (i,j+1) in one step.
  • He can step on the same tile only once. The tile at the initial position is assumed to have already been stepped on.

Each square has an integer value, and the score of a path is the sum of the values of the visited squares, including the square at the initial position. Your goal is to find a path with as high a score as possible.

Examples

Of the above three figures, only the path in the left figure satisfies the conditions. In the middle figure, the same tile is stepped on twice in a row. In the right figure, he left a tile once and then came back to the same tile.

Visualization result of the sample output. The red circle represents the initial position, and the green circle represents the final position. The tiles stepped on are painted in light blue.

Scoring

The score of the output path is the score for the test case. If the output does not satisfy the conditions, it is judged as WA. There are 100 test cases, and the score of a submission is the total score for each test case. If you get a result other than AC for one or more test cases, the score of the submission will be zero. The highest score obtained during the contest time will determine the final ranking, and there will be no system test after the contest. If more than one participant gets the same score, the ranking will be determined by the submission time of the submission that received that score.

Input

Input is given from Standard Input in the following format:

si sj
t_{0,0} t_{0,1} \ldots t_{0,49}
\vdots
t_{49,0} t_{49,1} \ldots t_{49,49}
p_{0,0} p_{0,1} \ldots p_{0,49}
\vdots
p_{49,0} p_{49,1} \ldots p_{49,49}
  • (si,sj) denotes the initial position and satisfies 0\leq si,sj\leq 49.
  • t_{i,j} is an integer representing the tile placed on (i,j). (i,j) and (i',j') are covered by the same tile if and only if t_{i,j}=t_{i',j'} holds. Let the total number of tiles be M, then 0\leq t_{i,j}\leq M-1 is satisfied.
  • p_{i,j} is an integer value satisfying 0\leq p_{i,j}\leq 99 which represents the score obtained when visiting (i,j).

Output

Let U, D, L, and R represent the movement from (i,j) to (i-1,j), (i+1,j), (i,j-1), and (i,j+1), respectively. Output a string representing a path in one line.

Input Generation

Generation of si,sj

Generate an integer between 0 and 49 uniformly at random.

Generation of t_{i,j}

We start from an initial configuration where tiles of size 1\times 1 are placed on all squares. We shuffle the 50x50 squares in random order and perform the following process for each square in order.

  • If the tile placed on the current square is 1\times 1, we randomly select one of the adjacent squares whose tile is 1\times 1 and connect the two tiles into one tile. If there are no such adjacent squares, we do nothing.
  • If the tile placed on the current square is not 1\times 1, we do nothing.

Generation of p_{i,j}

Generate an integer between 0 and 99 uniformly at random independently for each square.

Tools

  • Inputs: A set of 100 inputs (seed 0-99) for local testing, including the sample input (seed 0). These inputs are different from the actual test case.
  • Visualizer on the web
  • Input generator and visualizer: If you want to use more inputs, or if you want to visualize your output locally, you can use this program. You need a compilation environment of Rust language.

Sample Input 1

1 49
0 1 2 2 3 3 4 5 6 7 8 8 9 9 10 10 11 11 12 12 13 13 14 15 16 16 17 18 19 19 20 21 22 23 23 24 25 26 27 27 28 28 29 29 30 31 31 32 33 34
0 1 35 35 36 37 37 5 6 7 38 39 39 40 41 42 43 43 44 44 45 45 14 46 47 47 17 18 48 49 20 21 22 50 51 24 25 52 53 54 54 55 56 57 30 58 59 59 33 34
60 61 62 63 36 64 65 65 66 67 67 68 69 69 41 42 70 71 71 72 73 74 74 46 75 75 76 76 48 77 77 78 79 50 51 80 80 52 53 81 81 82 56 83 83 58 84 85 86 86
60 61 62 63 87 64 88 89 66 90 91 68 92 93 94 94 95 95 96 96 73 97 97 98 99 99 100 101 102 103 103 78 79 104 104 105 106 106 107 108 108 82 109 109 110 110 84 85 111 111
112 113 114 115 87 116 88 117 117 90 91 118 118 93 119 120 121 122 123 124 124 125 125 98 126 127 100 101 102 128 128 129 129 130 130 105 131 132 132 133 134 135 135 136 137 138 139 140 141 141
112 113 114 115 142 116 143 144 144 145 146 147 148 148 119 149 121 122 123 150 150 151 151 152 126 153 154 155 155 156 157 157 158 158 159 159 160 161 161 162 134 163 163 164 137 138 139 165 165 166
167 168 169 170 170 171 143 172 172 145 146 173 174 175 176 149 177 177 178 179 179 180 180 152 181 153 154 182 182 156 183 183 184 184 185 185 160 186 186 162 187 188 189 164 190 191 192 193 194 166
195 168 196 196 197 171 198 199 199 200 201 173 174 175 176 202 203 203 204 204 205 206 207 208 208 209 210 210 211 211 212 212 213 213 214 215 216 216 217 218 218 188 189 219 190 191 192 193 194 220
195 221 222 223 224 224 198 225 226 200 201 227 228 228 229 230 231 231 232 233 233 206 234 235 236 209 237 238 238 239 240 241 242 242 214 215 243 243 244 244 245 246 246 219 247 247 248 248 249 220
250 250 222 251 251 252 253 253 226 254 255 227 256 256 229 230 257 257 258 259 259 260 234 235 236 261 262 263 264 239 265 241 266 267 268 269 270 271 272 272 245 273 274 274 275 275 276 276 277 277
278 279 279 280 280 252 281 281 282 254 255 283 283 284 285 286 286 287 258 288 288 289 290 291 291 261 262 263 292 293 265 294 266 267 268 295 270 271 296 297 297 298 298 299 300 301 301 302 303 303
304 304 305 306 307 308 309 309 282 310 310 311 311 284 312 312 313 314 314 315 315 289 290 316 317 318 319 319 292 293 320 321 321 322 323 295 324 324 296 325 325 326 326 299 300 327 327 328 328 329
330 331 331 306 307 308 332 332 333 333 334 334 335 336 337 338 313 339 339 340 341 342 342 316 317 318 343 343 344 344 320 345 346 322 323 347 348 349 349 350 351 352 353 354 355 355 356 356 357 357
330 358 359 360 360 361 361 362 363 363 364 364 335 365 337 338 366 367 368 368 341 369 370 370 371 371 372 372 373 374 374 345 346 375 376 347 348 377 378 379 351 352 353 354 380 380 381 382 383 384
385 386 359 387 387 388 389 362 390 390 391 392 392 365 393 393 366 367 394 394 395 396 396 397 397 398 399 400 373 401 401 402 403 375 376 404 404 377 378 379 405 405 406 407 407 408 381 409 383 384
385 386 410 411 412 388 389 413 414 414 391 415 416 417 418 419 419 420 420 421 422 422 423 424 425 425 399 426 426 427 427 402 403 428 429 429 430 430 431 432 432 433 406 434 434 435 435 409 436 437
438 438 439 411 440 440 441 442 443 443 444 445 416 417 446 446 447 448 448 421 449 450 451 424 452 452 453 453 454 455 456 457 457 428 458 458 459 460 461 462 463 463 464 465 465 466 467 467 436 437
468 469 439 470 471 472 473 442 474 475 475 445 476 477 478 478 447 479 479 480 449 450 451 481 482 482 483 483 454 455 456 484 485 486 487 487 459 460 461 488 489 490 464 491 492 492 493 493 494 495
468 496 497 497 471 472 473 498 474 499 500 500 476 477 501 501 502 503 504 480 505 505 506 481 507 508 508 509 510 511 511 484 485 486 512 513 513 514 514 488 489 490 515 491 516 517 517 518 519 495
520 496 521 522 522 523 524 525 526 527 528 529 530 531 531 532 533 503 504 534 535 535 536 537 507 538 538 509 539 539 540 540 541 542 542 543 544 544 545 546 546 547 548 548 516 549 549 518 519 550
520 551 521 552 553 554 524 525 526 527 528 529 555 556 556 532 533 557 558 534 559 559 536 560 561 562 562 563 564 565 566 566 567 568 568 569 570 571 572 573 574 547 575 576 577 577 578 578 579 579
580 551 581 552 553 554 582 582 583 584 584 585 555 586 586 587 587 557 558 588 588 589 590 560 591 592 593 563 564 594 594 595 567 596 596 569 570 597 572 573 574 598 598 576 599 600 600 601 602 603
580 604 604 605 606 607 608 609 583 610 610 611 612 613 614 614 615 616 616 617 618 618 590 619 591 620 593 621 622 623 623 595 624 625 625 626 627 597 628 628 629 629 630 630 599 631 631 601 602 603
632 632 633 605 606 634 608 609 635 635 636 611 612 613 637 637 615 638 638 617 639 640 640 619 641 620 642 621 622 643 643 644 624 645 645 626 627 646 647 648 649 649 650 650 651 651 652 653 653 654
655 655 633 656 656 634 657 657 658 659 636 660 660 661 661 662 662 663 663 664 639 665 665 666 641 667 642 668 668 669 669 644 670 671 672 673 673 674 647 648 675 675 676 677 677 678 678 679 680 654
681 682 682 683 684 684 685 685 658 686 686 687 688 688 689 690 691 692 692 664 693 693 694 694 695 667 696 696 697 697 698 698 670 671 672 699 700 674 701 701 702 703 703 704 704 705 705 679 706 707
708 709 710 683 711 712 712 713 714 715 716 717 717 718 719 690 691 720 720 721 721 722 722 723 695 724 725 725 726 726 727 728 729 729 730 730 700 731 732 732 702 733 734 735 736 736 737 738 706 707
708 709 710 739 739 740 741 713 714 715 716 742 742 743 719 744 744 745 746 747 748 749 750 751 752 753 753 754 754 755 755 728 756 756 757 758 759 759 760 761 761 733 734 735 762 763 737 738 764 764
765 766 766 767 768 740 769 770 771 772 773 774 774 743 775 775 776 745 746 747 748 749 750 751 752 777 777 778 778 779 779 780 780 781 757 758 782 782 783 784 785 786 786 787 787 763 788 788 789 789
765 790 791 767 768 792 769 770 771 772 793 794 795 795 796 796 797 797 798 799 799 800 800 801 802 802 803 803 804 804 805 805 806 806 807 808 808 809 783 784 810 811 812 812 813 814 815 816 816 817
818 818 791 819 819 792 820 821 821 822 793 794 823 824 824 825 826 826 798 827 828 828 829 801 830 831 831 832 832 833 834 835 835 836 836 837 837 809 838 838 810 811 839 840 813 814 815 841 842 842
843 844 845 845 846 846 820 847 848 822 849 849 823 850 851 825 852 852 853 853 854 855 829 856 857 858 858 859 859 833 860 860 861 861 862 862 863 863 864 864 865 866 839 840 867 868 869 841 870 870
843 844 871 871 872 873 874 847 848 875 876 876 877 850 878 879 880 881 882 883 854 884 884 856 857 885 886 886 887 887 888 889 890 890 891 891 892 893 894 895 865 866 896 896 867 868 869 897 897 898
899 900 900 901 902 873 903 903 904 905 906 906 877 907 878 879 880 881 882 883 908 909 909 910 910 885 911 911 912 912 888 889 913 914 915 916 892 917 894 918 918 919 920 920 921 921 922 923 923 898
899 924 924 901 902 925 926 927 927 905 928 929 930 930 931 931 932 933 933 934 935 935 936 937 937 938 938 939 940 941 941 942 942 914 915 916 943 917 944 945 945 919 946 947 947 948 948 949 950 950
951 951 952 953 954 925 926 955 956 956 928 957 958 959 959 960 961 962 963 963 964 964 965 966 967 968 969 970 940 971 972 973 973 974 974 975 976 977 978 979 979 980 946 981 981 982 982 949 983 983
984 985 952 953 954 986 987 955 988 989 990 957 991 991 992 992 961 993 994 995 995 996 965 966 967 968 969 970 997 971 972 998 999 999 1000 1001 976 977 978 1002 1002 980 1003 1003 1004 1005 1006 1006 1007 1008
984 1009 1009 1010 1011 986 987 1012 1012 989 990 1013 1013 1014 1015 1016 1017 993 994 1018 1019 996 1020 1020 1021 1022 1022 1023 1023 1024 1025 998 1026 1027 1000 1001 1028 1029 1030 1030 1031 1032 1032 1033 1004 1005 1034 1035 1007 1036
1037 1037 1038 1010 1011 1039 1039 1040 1040 1041 1042 1043 1043 1014 1015 1016 1017 1044 1044 1018 1045 1046 1047 1047 1021 1048 1049 1050 1050 1051 1025 1052 1052 1027 1053 1054 1054 1029 1055 1055 1031 1056 1056 1033 1057 1057 1034 1058 1058 1036
1059 1060 1060 1061 1061 1062 1062 1063 1064 1041 1042 1065 1066 1067 1068 1068 1069 1070 1070 1071 1045 1046 1072 1072 1073 1048 1049 1074 1075 1051 1076 1077 1077 1078 1079 1079 1080 1081 1082 1082 1083 1084 1084 1085 1085 1086 1087 1088 1089 1090
1059 1091 1092 1093 1094 1095 1095 1063 1096 1097 1097 1065 1066 1098 1098 1099 1100 1100 1101 1102 1102 1103 1104 1105 1106 1106 1107 1107 1075 1108 1109 1109 1110 1078 1111 1112 1080 1113 1114 1115 1083 1116 1117 1118 1119 1120 1087 1088 1089 1090
1121 1091 1092 1093 1122 1122 1123 1123 1096 1124 1125 1126 1127 1127 1128 1099 1129 1129 1130 1130 1131 1132 1104 1105 1133 1133 1134 1134 1135 1135 1136 1136 1137 1137 1111 1112 1138 1113 1114 1115 1139 1116 1117 1118 1119 1120 1140 1140 1141 1142
1121 1143 1143 1144 1144 1145 1145 1146 1146 1124 1125 1126 1147 1147 1148 1148 1149 1150 1151 1152 1131 1132 1153 1154 1155 1155 1156 1157 1158 1159 1160 1160 1161 1161 1162 1163 1164 1165 1166 1166 1139 1167 1168 1169 1170 1170 1171 1171 1141 1142
1172 1173 1174 1175 1176 1177 1178 1178 1179 1180 1181 1181 1182 1183 1184 1185 1149 1150 1186 1152 1187 1187 1153 1154 1188 1188 1156 1157 1189 1159 1190 1191 1191 1192 1162 1193 1164 1165 1194 1195 1195 1167 1168 1169 1196 1196 1197 1197 1198 1198
1172 1173 1174 1175 1176 1199 1199 1200 1179 1180 1201 1201 1182 1202 1184 1185 1203 1203 1186 1204 1204 1205 1206 1207 1208 1208 1209 1210 1189 1211 1190 1212 1213 1192 1214 1193 1215 1216 1216 1217 1218 1218 1219 1220 1220 1221 1221 1222 1222 1223
1224 1225 1225 1226 1226 1227 1227 1228 1229 1229 1230 1231 1231 1202 1232 1233 1233 1234 1234 1235 1236 1237 1206 1238 1238 1239 1239 1210 1240 1240 1241 1212 1242 1243 1243 1244 1215 1245 1246 1247 1248 1249 1219 1250 1251 1251 1252 1253 1253 1223
1224 1254 1254 1255 1256 1256 1257 1228 1258 1258 1230 1259 1259 1260 1261 1262 1263 1264 1265 1235 1266 1237 1267 1268 1269 1270 1270 1271 1272 1273 1274 1275 1242 1276 1277 1244 1278 1245 1246 1247 1248 1279 1279 1280 1280 1281 1252 1282 1283 1284
1285 1286 1286 1255 1287 1288 1289 1289 1290 1291 1291 1292 1292 1260 1261 1262 1263 1264 1265 1293 1266 1294 1295 1268 1269 1296 1296 1297 1272 1273 1274 1298 1298 1276 1277 1299 1300 1300 1301 1301 1302 1302 1303 1303 1304 1281 1305 1282 1283 1284
1285 1306 1306 1307 1308 1288 1309 1309 1310 1310 1311 1311 1312 1313 1313 1314 1315 1315 1316 1293 1317 1318 1295 1319 1319 1320 1321 1297 1322 1322 1323 1324 1324 1325 1325 1299 1326 1327 1328 1329 1330 1331 1332 1332 1304 1333 1334 1335 1336 1337
1338 1338 1339 1307 1308 1340 1340 1341 1342 1342 1343 1343 1312 1344 1344 1345 1345 1346 1316 1347 1317 1318 1348 1348 1349 1320 1321 1350 1351 1351 1323 1352 1352 1353 1354 1354 1326 1327 1328 1329 1330 1331 1355 1355 1356 1356 1334 1335 1336 1337
50 22 28 77 64 20 0 38 74 88 84 50 15 38 97 45 37 2 24 37 90 97 44 67 65 38 11 76 21 62 23 83 7 33 47 64 90 25 11 40 20 71 48 14 78 2 61 84 62 58
54 31 65 33 17 71 22 54 66 28 40 18 19 25 13 53 22 70 62 80 27 28 30 97 69 32 79 76 13 25 98 86 48 6 92 67 13 28 11 7 55 67 86 18 4 61 15 15 32 11
60 34 56 43 0 39 66 0 75 89 52 71 93 40 53 13 63 46 34 58 1 89 75 32 75 95 27 61 88 79 74 71 37 39 67 6 72 13 85 33 83 9 61 96 18 35 20 5 90 30
97 72 96 6 71 9 25 66 44 95 60 5 5 7 10 51 39 75 41 19 6 71 34 76 10 71 32 78 32 75 32 34 9 25 2 62 53 47 68 34 89 15 29 85 0 59 75 14 90 28
32 45 33 78 53 12 88 81 26 22 33 82 10 63 46 56 96 47 44 47 45 81 66 50 84 87 4 40 46 2 95 63 90 83 4 8 37 89 73 47 79 97 4 99 34 25 37 22 29 19
90 19 97 46 41 81 13 11 80 54 88 79 76 37 86 0 89 39 41 79 33 57 18 10 22 58 65 53 46 20 22 90 13 82 77 6 28 42 73 21 55 69 34 48 23 32 98 79 41 17
90 47 92 61 8 18 2 79 30 48 17 56 81 84 1 51 31 23 71 90 38 91 76 51 29 19 32 50 92 55 89 77 23 40 0 87 4 52 38 55 89 61 87 40 32 21 98 42 71 23
39 72 50 44 10 78 66 55 58 91 67 63 66 39 15 52 38 67 95 79 47 41 87 46 9 61 65 6 0 17 74 49 99 80 35 36 67 4 59 46 70 3 95 61 39 5 51 22 82 10
71 93 13 69 73 60 68 40 84 19 53 12 64 91 79 66 3 42 13 93 78 72 26 46 50 5 38 41 42 27 47 35 2 75 99 16 77 25 67 70 66 40 2 48 8 60 46 34 45 78
59 77 22 49 20 73 64 58 44 19 73 8 13 48 15 72 5 82 22 57 88 63 59 36 33 21 80 64 40 28 60 71 63 89 67 10 8 43 10 18 31 28 10 19 25 40 56 84 15 1
5 7 63 62 47 32 7 29 41 51 21 73 21 43 99 65 22 7 97 49 86 5 13 51 56 62 12 23 34 93 36 3 52 55 49 45 1 40 26 96 51 1 73 45 36 33 1 74 86 32
63 54 29 70 87 98 69 19 31 88 11 87 5 31 24 17 26 36 9 41 6 59 11 54 49 84 34 43 66 43 20 12 75 68 24 4 20 24 9 47 64 5 2 45 75 42 90 32 83 85
73 87 73 10 91 44 92 61 90 51 57 66 94 58 15 20 68 51 69 13 41 43 33 85 1 21 30 50 8 82 47 10 79 83 86 98 85 5 8 68 92 84 78 64 40 47 12 64 46 32
26 21 88 56 79 90 87 86 86 46 91 93 50 50 72 48 62 57 32 74 49 23 66 9 7 73 17 35 52 51 29 80 64 64 76 22 63 86 55 99 17 92 87 20 40 44 79 51 55 78
69 24 52 79 6 76 31 3 14 22 16 5 45 77 11 80 52 73 95 71 88 51 78 32 21 78 78 7 67 20 27 7 11 33 15 78 43 35 64 68 36 81 87 74 33 18 74 7 87 4
67 16 66 23 84 66 30 36 87 93 60 47 22 19 1 97 67 43 70 29 82 15 73 16 76 96 9 95 31 45 36 46 47 68 90 56 77 70 49 78 40 36 17 90 55 66 58 20 43 46
27 2 1 27 57 23 54 93 87 24 88 41 55 3 22 54 72 69 41 43 45 58 95 65 92 9 66 49 16 96 8 56 82 34 1 43 4 77 15 63 88 86 73 95 53 52 90 86 94 49
42 38 70 49 40 6 67 34 40 60 21 54 0 47 2 2 1 79 8 41 45 32 62 92 82 49 9 87 63 15 11 51 12 32 3 25 39 34 12 33 34 57 73 97 69 64 80 68 28 77
12 93 99 20 9 33 76 73 82 40 31 10 70 6 0 83 90 0 93 69 23 94 91 50 28 39 93 26 70 72 32 28 14 55 96 24 38 33 79 50 79 91 62 27 90 24 94 5 15 4
89 8 31 0 0 60 47 37 96 9 84 0 39 4 64 40 74 58 25 61 71 47 49 50 44 46 82 65 38 65 99 14 27 24 45 45 17 55 21 37 35 38 62 87 13 21 27 93 55 76
0 36 73 89 13 98 19 18 97 92 74 22 0 74 6 22 35 6 2 73 80 36 1 65 54 82 98 65 40 11 86 70 80 52 85 3 36 31 73 29 71 12 27 70 78 5 41 71 86 77
57 80 18 3 78 32 52 14 88 17 92 49 55 58 95 49 56 2 65 7 56 42 51 98 69 26 69 18 95 84 71 48 32 23 70 68 58 46 25 57 29 10 4 66 31 14 38 15 61 34
69 58 40 38 98 37 39 25 84 4 87 9 95 37 9 63 5 81 71 74 50 86 44 10 33 66 25 44 94 7 81 70 25 62 65 94 11 15 98 23 41 71 45 82 6 43 78 78 58 93
56 69 38 53 13 28 58 46 8 97 18 39 84 57 9 68 38 8 23 66 41 27 98 45 77 64 83 17 67 30 15 39 36 84 50 21 22 54 42 98 86 1 95 97 66 98 53 34 17 91
44 50 17 76 79 52 91 68 21 24 30 51 57 81 74 88 70 46 85 2 29 16 13 39 54 10 62 67 83 50 7 73 44 42 10 51 25 39 53 51 49 12 13 78 53 73 31 6 64 20
45 88 62 61 41 77 8 33 22 81 44 75 1 24 2 22 20 63 50 7 48 55 16 8 59 88 87 13 75 79 78 89 74 97 39 85 42 99 24 14 14 18 11 51 48 3 61 94 30 50
82 83 15 71 63 1 5 99 39 70 15 72 85 28 64 64 50 7 61 82 95 78 20 18 16 41 16 56 21 1 53 37 74 16 47 49 6 36 17 16 40 1 90 69 77 97 58 64 94 54
4 4 63 94 85 76 46 72 78 26 2 11 1 21 82 65 71 3 37 22 87 3 59 52 52 20 75 83 68 59 48 99 77 65 14 41 96 71 81 72 28 16 10 0 58 25 12 43 48 13
20 91 6 64 82 82 60 39 50 42 56 75 13 92 44 76 53 69 93 6 80 82 25 39 39 9 10 85 32 48 1 7 96 92 75 6 83 66 61 50 78 61 71 82 82 80 7 52 68 21
78 43 31 32 81 86 47 75 20 20 75 46 95 54 44 74 34 88 56 69 53 66 65 43 8 38 76 71 65 77 81 83 50 75 42 83 87 82 85 83 26 8 60 74 65 72 31 38 32 44
59 22 25 85 23 7 73 25 4 43 63 45 57 71 91 90 94 80 46 39 26 44 4 12 81 73 4 76 5 44 23 94 6 28 22 65 81 26 27 33 90 72 86 82 43 35 90 8 91 65
70 39 90 65 83 36 62 44 33 58 16 2 75 4 90 48 13 62 26 15 82 87 76 41 96 97 89 12 29 28 68 59 80 52 70 2 47 68 47 66 64 27 12 61 53 95 11 91 27 21
94 46 29 29 93 22 11 82 44 47 53 73 0 72 85 7 91 66 36 65 66 72 1 10 63 74 24 75 26 75 56 61 87 53 40 29 2 54 2 64 18 22 8 81 86 40 78 42 19 27
23 96 2 50 52 30 86 70 98 52 61 47 6 47 75 15 24 70 38 41 77 18 79 85 46 65 57 11 57 4 7 34 8 25 81 48 69 94 27 71 13 58 78 28 10 35 32 5 58 35
80 96 65 43 84 78 3 3 16 28 47 85 11 74 66 47 70 63 37 78 91 40 63 29 22 59 47 46 87 15 20 95 1 79 7 16 94 76 4 84 31 1 47 33 85 52 98 59 7 75
88 59 64 16 74 81 4 58 14 65 85 28 76 59 9 53 10 39 25 98 46 7 75 58 73 46 4 43 40 50 9 40 19 7 56 5 55 22 55 89 75 32 19 30 23 17 99 28 57 24
1 80 29 51 34 87 99 28 80 17 67 60 5 46 68 92 31 79 46 18 39 39 16 20 96 58 91 25 3 1 47 53 30 2 69 49 0 18 9 82 16 68 51 54 43 18 37 82 55 11
18 76 63 42 9 13 48 23 50 4 11 28 32 16 7 2 9 46 53 93 25 86 63 55 82 81 15 71 39 97 93 63 96 48 71 79 39 32 29 60 14 55 57 18 77 32 4 57 83 74
91 83 23 16 51 25 60 54 50 49 10 67 65 78 17 79 88 2 40 76 80 77 31 16 82 62 34 60 15 45 22 35 34 87 45 27 25 9 61 78 17 17 19 76 94 58 47 47 63 37
76 98 70 13 45 49 76 4 29 45 11 3 56 36 58 4 93 80 60 60 48 13 66 87 20 85 2 12 54 1 7 59 61 33 95 69 73 63 13 9 13 68 14 99 56 17 88 48 71 40
52 61 71 60 66 91 49 73 17 33 15 7 65 66 62 79 70 50 7 25 8 29 3 93 4 4 13 71 27 0 23 91 57 70 51 50 79 92 22 35 87 30 3 52 4 5 94 28 35 45
82 35 3 85 21 10 56 32 84 7 31 34 16 78 34 79 23 9 84 78 75 64 64 51 48 19 11 98 87 94 75 55 5 3 10 2 73 57 75 50 21 47 70 64 97 96 47 66 91 34
78 46 96 45 78 31 78 9 16 52 14 42 98 23 80 99 69 60 83 51 45 64 27 75 65 23 26 63 17 4 70 71 21 38 94 27 48 65 58 78 72 45 49 27 43 14 76 3 28 65
47 83 28 63 1 28 83 82 18 92 91 87 53 76 77 82 7 1 37 92 91 63 44 24 0 12 24 74 13 73 84 81 53 5 85 9 62 84 73 71 85 0 7 64 30 49 95 62 80 15
16 74 78 31 47 55 33 38 70 33 34 12 50 57 49 14 4 22 79 35 74 18 58 63 58 40 18 69 81 79 46 33 3 81 25 89 26 42 49 10 52 58 8 48 30 9 47 19 94 22
31 38 59 13 55 81 2 33 81 61 20 7 36 63 61 65 62 68 5 12 58 80 8 8 30 14 30 50 6 24 77 65 11 1 64 67 45 39 19 26 45 60 93 77 2 24 34 14 60 50
40 36 77 19 56 97 42 38 30 71 68 82 70 42 37 56 71 22 78 52 43 0 87 30 64 18 47 55 10 25 48 83 95 57 65 89 63 69 59 88 74 20 57 75 19 21 65 4 93 93
77 35 97 44 2 93 82 76 96 84 14 70 98 41 58 82 67 74 15 1 77 84 52 10 22 58 65 99 16 35 14 34 65 3 92 32 43 29 56 73 97 30 66 86 56 99 82 45 83 97
73 88 13 17 24 43 70 18 65 61 46 21 8 68 82 64 81 87 1 33 8 56 54 84 8 66 92 40 89 80 22 41 50 10 0 25 97 13 40 0 80 95 60 4 60 51 2 0 51 68
49 69 41 45 58 41 33 92 20 45 23 57 43 44 30 83 37 75 0 46 27 90 23 45 3 75 42 19 74 61 26 49 52 80 36 93 98 70 15 52 10 26 95 32 1 47 97 8 79 69

Sample Output 1

LDDDDDLLULLLUUULLLDDRDDLDDLDDDDDLLLDDLDDRDRDDRRRUURRURUUULULDDD