Problem Description

There is a map consisting of $ H $ rows and $ W $ columns of squares. Among them, $ K $ squares contain one car each.

The top row is considered as row $ 1 $, the leftmost column as column $ 1 $, and the square at row $ r $ and column $ c $ is denoted as $ (r, c) $.

Each of the $ K $ cars is given an initial square (referred to as the initial square) and a destination square (referred to as the destination square). The initial square of car $ i $ is $ (A_i, B_i) $. Also, the destination square of car $ i $ is $ (C_i, D_i) $. You can instruct each car to move to an adjacent square by edge at each time $ t $ ($0 \leq t < L$, $ t $ is an integer). As a result, at time $ t+1 $, the car will move to the instructed square. However, the following movements cannot be instructed:

• If the destination square already contains a car at time $ t $
• If multiple cars have the same destination square simultaneously
• If the destination square is outside the map

In one instruction, you can instruct all $ K $ cars to move to one of the four adjacent directions or stay in the current square. You can issue a maximum of $ T $ instructions.

The score for each test case and the score for this problem are calculated as follows:

• Let the final position of car $ i $ be $ (r_i, c_i) $, and let
• Let the number of instructions be $L\ (0 \leq L \leq T)$, then $P_T = 10 + L \times 0.01$.
• $= 10^7 / (P_D \times P_T)$
• The final score for that test case is the ceiling of the calculated $ score $.
• There are a total of $ 30 $ test cases. The sum of the scores for each test case is the score for this problem.

Please issue appropriate instructions to maximize the score.

Input Format

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

$ H $ $ W $ $ K $ $ T $ $ A_1 $ $ B_1 $ $ C_1 $ $ D_1 $ $ A_2 $ $ B_2 $ $ C_2 $ $ D_2 $ : $ A_K $ $ B_K $ $ C_K $ $ D_K $

• $ H $ is an integer representing the number of rows in the map, satisfying $ H=30 $.
• $ W $ is an integer representing the number of columns in the map, satisfying $ W=30 $.
• $ K $ is an integer representing the number of cars on the map, satisfying $ K=450 $.
• $ T $ is an integer representing the maximum number of instructions that can be issued to the cars, satisfying $ T=10,000 $.
• $ A_i $ and $ B_i $ are integers representing the initial square $ (A_i, B_i) $ of car $ i $, satisfying $1 \leq A_i \leq H$, $1 \leq B_i \leq W$.
• $ C_i $ and $ D_i $ are integers representing the destination square $ (C_i, D_i) $ of car $ i $, satisfying $1 \leq C_i \leq H$, $1 \leq D_i \leq W$.
• If $i \neq j$, then $(A_i, B_i) \neq (A_j, B_j)$ and $(C_i, D_i) \neq (C_j, D_j)$.

Output Format

Output to standard output in the following format:

$ L $ $ movement_0 $ $ movement_1 $ : $ movement_{L-1} $

• On the first line, output the number of instructions $L\ (0 \leq L \leq T)$.
• On the $t+2\ (0 \leq t < L)$ line, output the string $ movement_t $ representing the instructions issued to each car at time $ t $.
• $movement_t\ (0 \leq t < L)$ is a string of $ K $ characters, where the $ i $ character represents the instruction issued to car $ i $.
• Each instruction is represented by the following characters: U Move to the square one row smaller (up). D Move to the square one row larger (down). L Move to the square one column smaller (left). R Move to the square one column larger (right). - Stay in the current square.

Sample Input and Output

Sample Input #1

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

Sample Output #1

4
RR
RU
DU
-L

Sample Input #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 3

见题面 Input 部分

见题面 Output 部分