Problem Description

There is a square map with $H$ rows and $W$ columns. Each cell on the map is either an obstacle cell or an empty cell. Some empty cells have at most one piece of food placed on them.

The first row is considered the $1$st row, and the first column is considered the $1$st column. A dog is initially located at the cell in the $sr$th row and $sc$th column of the map. The dog can move to adjacent cells (excluding obstacle cells) at $0, 1, 2, \ldots$ seconds after the start. The dog's movement is assumed to be instantaneous. When the dog moves to a cell with food, it always collects the food. Upon collecting the food, the food disappears from that cell, and you gain the corresponding score for the food. The initial score of food $i$ is $F_i$, which decreases by $D_i$ every second. The decrease occurs immediately after the dog moves and collects the food.

Output the actions of the dog from $0, 1, 2, \ldots, K-1$ seconds after the start to maximize the score.

Input Format

The input is given from the standard input in the following format. All inputs are integers.

$H$ $W$ $K$ $sr$ $sc$ $s_1$ $s_2$ : $s_H$ $N$ $fr_1$ $fc_1$ $F_1$ $D_1$ $fr_2$ $fc_2$ $F_2$ $D_2$ : $fr_N$ $fc_N$ $F_N$ $D_N$

• $H = W = 50$
• $K = 2500$
• $1 \leq sr \leq H$
• $1 \leq sc \leq W$
• $s_i$ ($1 \leq i \leq H$) is a string of length $W$ representing the $i$th row of the map, consisting of # and ..
• # represents an obstacle cell.
• . represents an empty cell.
• $N$ represents the number of cells with food.
• $1 \leq fr_i \leq H$ ($1 \leq i \leq N$).
• $1 \leq fc_i \leq W$ ($1 \leq i \leq N$).
• $0 \leq F_i \leq 10^5$ ($1 \leq i \leq N$).
• $0 \leq D_i \leq 100$ ($1 \leq i \leq N$).
• $fr_i, fc_i$ represent the row and column of the cell with food.
• $F_i, D_i$ represent the initial score and the decrease score per second of the food.
• $(sr, sc), (fr_i, fc_i)$ are distinct, and they always point to empty cells.
• The edges of the map (1st row, $H$th row, 1st column, $W$th column) are all obstacle cells.
• Any empty cell can be reached from any other empty cell by moving only through adjacent empty cells.

Output Format

Output to the standard output in the following format:

$movement$

• Output a string $movement$ of exactly $K$ characters on the first line.
• $movement$ is a string representing the dog's actions, consisting of the following characters: U moves to the cell one row up, D moves to the cell one row down, L moves to the cell one column left, R moves to the cell one column right, - does not move.

Sample Input and Output

Sample Input #1

10 10 20 4 9
##########
###.....##
##...##..#
#...####.#
#...######
#...######
#...######
#...######
#...######
##########
2
3 9 10000 5
3 3 4 1

Sample Output #1

ULRLULLLDLL-DDR-RRRR

Sample Input #2

50 50 2500 23 16
##################################################
###......#########.#.###.##.###.################.#
########.#########.#.###.##.###.################.#
########.#.....###.#........###.################.#
########.##.##.###................##############.#
###...................##.######.#.##############.#
###########.###.#..#..##.######.#.##############.#
###########.#...#..#...............#############.#
###########.#.#...............#.....##...........#
###########.###.#.#.#..#......#....###.###########
###########.#####.#.##.#........#..###.###########
###########.####................#..###.###########
###########.####....#........#..#.........########
#########...............................##########
##.######.######...................###..##########
#..######.#................#.#......##..##########
#..######.#..#.#........................##########
#.........................#..#......#...##########
#..........#..............#..#......#...##########
#..........#.....#......................##########
#...#..#...#.................#......#...##########
#..##..#.#.#........................#...##########
#..........##.......................#....#########
##.#.#.#.#.#...................#....#.......######
####.#.........................#....#...###.######
####.....................................##.######
####.........##.....#..........#..#.##...##.######
####.......................#......#.#.......######
#.##......##.#....................#.#....#########
#...................................#....#########
#.##.##...##.##.#........................#########
#.##.##...##.##.....................#....#########
#.##..................#.............#...##########
#....##....#........................#...##########
#...................................#...##########
#.......................................##########
##.#..##....###.##.#....................##########
####..##..#.###.##.#.##...#........#.#..##########
####..##..#.###.##.#.##...#.............##########
###.......#........#.##...#.#...####.#.###########
####..##..#####.####.##...#.#...#.........########
####..##..#####.####.##...#.#...#.####.##.########
####..##..#####.####......#.....#.###.....########
#####.###.#####.####..#.#.............###.########
#####.###.#####..###..####.##.#.#.#######.########
#####.###.#####..###..####.##.#.#.################
#.....###.####....##..####.#......################
#########..................##.......##############
####################.#..........#.################
##################################################
128
36 6 33421 59
28 14 59990 74
21 15 91235 96
35 21 27683 71
20 11 11576 6
30 18 1583 87
6 4 21368 56
9 16 96637 100
26 11 21283 33
31 8 20294 33
2 21 65091 29
19 22 18039 17
5 33 98990 34
24 18 6500 60
14 10 26823 20
25 28 85792 28
47 18 537 36
26 23 60156 38
28 15 17810 17
20 39 28088 77
33 31 49621 37
20 32 83255 24
4 49 17499 96
31 9 93800 85
18 35 75782 37
24 25 61216 36
23 35 11322 33
6 5 84247 43
12 26 97308 40
6 6 7020 93
25 44 48412 4
6 15 30741 93
28 40 60392 6
23 28 50081 46
5 27 27989 38
23 32 91705 72
12 23 26710 59
28 17 36863 94
20 36 12665 77
17 12 69103 43
19 2 22817 20
18 38 27069 40
10 25 89918 76
32 28 7871 14
35 24 40156 17
32 16 50330 35
35 16 94626 5
17 33 2103 94
48 34 87848 82
19 21 52841 86
2 9 47976 39
46 17 10653 70
4 15 28399 40
5 30 85741 4
16 20 66310 36
13 27 79008 52
25 13 53822 71
8 18 96550 51
39 34 29271 54
38 24 92830 30
38 34 90137 86
48 18 82174 6
24 9 96186 3
7 18 21405 19
16 23 53528 2
31 31 8980 90
23 14 6256 21
49 24 57192 21
30 38 29651 33
16 24 80144 66
39 19 71496 10
26 38 22365 82
16 27 94591 4
30 19 13375 52
48 22 13906 29
45 21 15200 100
17 24 73814 1
5 15 89249 49
43 31 12710 19
16 21 89488 33
17 29 70865 55
33 20 71412 100
19 40 96591 32
8 30 6866 40
34 3 68501 20
24 28 99184 74
31 38 60999 70
8 22 88203 87
21 19 55945 64
14 18 46530 68
33 27 90347 100
44 31 40042 4
8 16 25939 91
44 28 17446 7
43 32 30346 61
22 2 16138 39
17 32 23668 8
20 29 3455 11
21 38 10036 59
14 19 80874 52
24 23 25439 55
29 8 7661 89
32 26 86161 51
22 27 18200 72
40 10 13922 31
8 23 58303 73
24 40 57936 38
27 11 14252 62
37 19 18676 93
17 21 46494 63
20 14 87223 9
39 39 9764 8
20 3 74043 69
47 16 76510 86
20 31 74695 46
29 26 78237 53
28 13 12037 81
38 19 65664 100
40 13 62357 39
27 13 95311 27
34 13 2537 69
46 6 94570 43
23 5 65255 8
2 25 93842 49
18 28 29560 48
12 24 60028 98
36 30 40774 28
24 42 57689 22

Sample Output #2

```
LDUDURRLDLRURDLURRU-DR--RRURDLRDRDRUULUDRRUDDD-DLLDRDLRD-R-UU-R--L-ULURDU-DULRL-RUDUUR-URUURUD-RDLLLRRDUURLDURLD-R-LDLURUULRULRLDUURLRDLDLUULLLU-DL-DLD-U-DLLURDR-RUD-URRUDLU-RUU-URUDL-DLLUDRUUURUU--RRL-DR-RDUUUULURDRU--UDLLRLDRU-DLLU-DDLLUD-RRDRLD-UDDRDDUUDLUR--D-L-RUUUDR--LL-LUURLUD--UDRDDL--UDL-RRR-L-LRUDUDD----D-DRDLU-UU-RRD-DL-RR-LDDR-UDRRRUU-DDR-U-L-UDUULRDRDLLUD--D--LRUU-UUULU-DDDDLDRUDLDRURUURLDRL-L-RRDRD-LL-D-LD--RDRLDULLLD-L-L-URRURLURL-L--DR--RD-LLULRUDRLLUDDRUUDD-URLRRRLUD-URLD-UDDUURLLUUR-LDULDRRDRD-LD-LRL-R-D-DLDRDD-LLLLDDDULL--LLDDLU--DU---LLDRUL--LDD-UL-L-ULUDUDDULD-R-LUR-LDDDRDL-LULLULLDUULU-DRRU--DDUUDLDRU-U--UUURDD-----URDLUDRDULU-L-U-D-LUUURRLUDD-R-UL-DUD-LLRRUULRU-D-R-L--RDRLLLRLDUDDLU--DULLD-LLLLDRUUURURRR-RDUDLUD--U-R-ULRLR-UL-U-RDDRRRRRLR-RURRUD--UUDRULDLRLURLD-R-RL-ULLL-DLRDD-U-DUR-L--DU-DLDR-RLRL-LLDLRDRU-LRLDDRD-U-L-RRD---ULD-RRDULLURL-RLDUR-DD-DLRDU---LUDRR-L

见题面 Input 部分

见题面 Output 部分