Problem Statement
You are on an infinite grid. You are currently standing on the cell with coordinates (r1, c1). Your goal is to reach the cell with coordinates (r2, c2) in exactly s steps.
In each step you must move from your current cell into one of the four adjacent cells. The moves from (r, c) to (r-1, c) and (r+1, c) are denoted 'U' (up) and 'D' (down). The moves from (r, c) to (r, c-1) and (r, c+1) are denoted 'L' (left) and 'R' (right).
"Reaching the destination in exactly s steps" means that you are NOT allowed to step onto the destination sooner. After each of the earlier steps you must be on some other cell. You can only step on the cell (r2, c2) after making the s-th step. (See Example 2 for an extra clarification of a technical detail.)
If your goal cannot be reached, return "IMPOSSIBLE" (quotes for clarity). Otherwise, return any string of length s that uses the letters 'U', 'D', 'L', 'R' to describe one valid sequence of steps you can take.
Definition
- Class:
- GoThereExactly
- Method:
- walk
- Parameters:
- int, int, int, int, int
- Returns:
- String
- Method signature:
- String walk(int r1, int c1, int r2, int c2, int s)
- (be sure your method is public)
Notes
- Remember that the returned sequence must get you from (r1, c1) exactly to (r2, c2) without stepping on (r2, c2) along the way.
- There are no restrictions on how you can move along the grid. In particular, you may move to coordinates that are smaller and/or larger than those where you start and end your walk.
Constraints
- r1, c1, r2 and c2 will all be between 0 and 100, inclusive.
- s will be between 0 and 1,000, inclusive.
Examples
4
7
4
7
0
Returns: ""
Going from (4, 7) to (4, 7) in exactly zero steps is easy: just do nothing.
4
7
4
8
42
Returns: "IMPOSSIBLE"
Going from (4, 7) to (4, 8) in exactly 42 steps is impossible: no sequence of exactly 42 'U's, 'D's, 'L's and 'R's will get us there.
4
7
4
7
12
Returns: "UUURRRDDDLLL"
The example return value corresponds to walking along the boundary of a square. Note that this is a valid solution, even though it starts and ends in the same cell. The exact constraint we were given is that after each step except for the last one we must not be in the destination cell. This is true for our solution: after steps 1, 2, ..., 11 we are not on (4, 7), we only return back after step 12.
0
0
4
0
14
Returns: "LLDDRRDRRRDLLL"
0
0
4
4
6
Returns: "IMPOSSIBLE"
15
11
13
9
0
Returns: "IMPOSSIBLE"
16
18
14
16
1
Returns: "IMPOSSIBLE"
17
19
15
17
2
Returns: "IMPOSSIBLE"
15
14
13
12
3
Returns: "IMPOSSIBLE"
18
16
16
13
5
Returns: "UULLL"
16
19
14
17
5
Returns: "IMPOSSIBLE"
10
16
8
14
6
Returns: "DUUULL"
20
10
18
8
7
Returns: "IMPOSSIBLE"
11
10
9
9
0
Returns: "IMPOSSIBLE"
14
17
12
16
1
Returns: "IMPOSSIBLE"
18
10
16
9
2
Returns: "IMPOSSIBLE"
15
19
13
18
3
Returns: "UUL"
16
13
14
12
4
Returns: "IMPOSSIBLE"
13
18
11
17
5
Returns: "DUUUL"
18
15
16
14
6
Returns: "IMPOSSIBLE"
17
13
15
12
7
Returns: "DDUUUUL"
10
18
8
18
0
Returns: "IMPOSSIBLE"
15
15
13
15
1
Returns: "IMPOSSIBLE"
19
15
17
15
2
Returns: "UU"
18
19
16
19
3
Returns: "IMPOSSIBLE"
13
13
11
13
4
Returns: "DUUU"
10
12
8
12
5
Returns: "IMPOSSIBLE"
15
11
13
11
6
Returns: "DDUUUU"
15
19
13
19
7
Returns: "IMPOSSIBLE"
16
18
14
19
0
Returns: "IMPOSSIBLE"
18
14
16
15
1
Returns: "IMPOSSIBLE"
11
20
9
21
2
Returns: "IMPOSSIBLE"
13
15
11
16
3
Returns: "UUR"
13
17
11
18
4
Returns: "IMPOSSIBLE"
11
16
9
17
5
Returns: "DUUUR"
19
15
17
16
6
Returns: "IMPOSSIBLE"
20
14
18
15
7
Returns: "DDUUUUR"
13
18
11
20
0
Returns: "IMPOSSIBLE"
14
15
12
17
1
Returns: "IMPOSSIBLE"
18
19
16
21
2
Returns: "IMPOSSIBLE"
10
17
8
19
3
Returns: "IMPOSSIBLE"
14
19
12
21
4
Returns: "UURR"
16
14
14
16
5
Returns: "IMPOSSIBLE"
18
13
16
15
6
Returns: "DUUURR"
19
11
17
13
7
Returns: "IMPOSSIBLE"
20
13
19
11
0
Returns: "IMPOSSIBLE"
16
17
15
15
1
Returns: "IMPOSSIBLE"
14
19
13
17
2
Returns: "IMPOSSIBLE"
18
12
17
10
3
Returns: "ULL"
17
10
16
8
4
Returns: "IMPOSSIBLE"
12
18
11
16
5
Returns: "DUULL"
20
11
19
9
6
Returns: "IMPOSSIBLE"
11
14
10
12
7
Returns: "DDUUULL"
18
19
17
18
0
Returns: "IMPOSSIBLE"
18
17
17
16
1
Returns: "IMPOSSIBLE"
16
15
15
14
2
Returns: "UL"
10
19
9
18
3
Returns: "IMPOSSIBLE"
14
20
13
19
4
Returns: "DUUL"
19
18
18
17
5
Returns: "IMPOSSIBLE"
20
17
19
16
6
Returns: "DDUUUL"
20
15
19
14
7
Returns: "IMPOSSIBLE"
10
19
9
19
0
Returns: "IMPOSSIBLE"
13
13
12
13
1
Returns: "U"
15
16
14
16
2
Returns: "IMPOSSIBLE"
12
12
11
12
3
Returns: "DUU"
17
13
16
13
4
Returns: "IMPOSSIBLE"
12
11
11
11
5
Returns: "DDUUU"
12
19
11
19
6
Returns: "IMPOSSIBLE"
15
18
14
18
7
Returns: "DDDUUUU"
16
11
15
12
0
Returns: "IMPOSSIBLE"
14
17
13
18
1
Returns: "IMPOSSIBLE"
10
20
9
21
2
Returns: "UR"
11
16
10
17
3
Returns: "IMPOSSIBLE"
11
15
10
16
4
Returns: "DUUR"
10
14
9
15
5
Returns: "IMPOSSIBLE"
10
12
9
13
6
Returns: "DDUUUR"
12
18
11
19
7
Returns: "IMPOSSIBLE"
17
13
16
15
0
Returns: "IMPOSSIBLE"
17
18
16
20
1
Returns: "IMPOSSIBLE"
17
19
16
21
2
Returns: "IMPOSSIBLE"
19
10
18
12
3
Returns: "URR"
11
12
10
14
4
Returns: "IMPOSSIBLE"
12
18
11
20
5
Returns: "DUURR"
15
20
14
22
6
Returns: "IMPOSSIBLE"
10
19
9
21
7
Returns: "DDUUURR"
13
10
13
8
0
Returns: "IMPOSSIBLE"
16
11
16
9
1
Returns: "IMPOSSIBLE"
10
11
10
9
2
Returns: "LL"
14
10
14
8
3
Returns: "IMPOSSIBLE"
18
14
18
12
4
Returns: "UDLL"
13
19
13
17
5
Returns: "IMPOSSIBLE"
18
12
18
10
6
Returns: "UUDDLL"
18
19
18
17
7
Returns: "IMPOSSIBLE"
14
19
14
18
0
Returns: "IMPOSSIBLE"
19
11
19
10
1
Returns: "L"
19
17
19
16
2
Returns: "IMPOSSIBLE"
15
18
15
17
3
Returns: "UDL"
10
11
10
10
4
Returns: "IMPOSSIBLE"
16
16
16
15
5
Returns: "UUDDL"
15
14
15
13
6
Returns: "IMPOSSIBLE"
19
17
19
16
7
Returns: "UUUDDDL"
19
12
19
12
0
Returns: ""
11
18
11
18
1
Returns: "IMPOSSIBLE"
11
17
11
17
2
Returns: "UD"
20
17
20
17
3
Returns: "IMPOSSIBLE"
10
16
10
16
4
Returns: "UUDD"
19
18
19
18
5
Returns: "IMPOSSIBLE"
11
14
11
14
6
Returns: "UUUDDD"
17
18
17
18
7
Returns: "IMPOSSIBLE"
11
13
11
14
0
Returns: "IMPOSSIBLE"
15
15
15
16
1
Returns: "R"
12
17
12
18
2
Returns: "IMPOSSIBLE"
10
19
10
20
3
Returns: "UDR"
11
20
11
21
4
Returns: "IMPOSSIBLE"
17
17
17
18
5
Returns: "UUDDR"
14
20
14
21
6
Returns: "IMPOSSIBLE"
18
20
18
21
7
Returns: "UUUDDDR"
10
18
10
20
0
Returns: "IMPOSSIBLE"
13
20
13
22
1
Returns: "IMPOSSIBLE"
14
10
14
12
2
Returns: "RR"
14
18
14
20
3
Returns: "IMPOSSIBLE"
17
16
17
18
4
Returns: "UDRR"
11
11
11
13
5
Returns: "IMPOSSIBLE"
18
19
18
21
6
Returns: "UUDDRR"
19
17
19
19
7
Returns: "IMPOSSIBLE"
18
15
19
13
0
Returns: "IMPOSSIBLE"
19
14
20
12
1
Returns: "IMPOSSIBLE"
16
20
17
18
2
Returns: "IMPOSSIBLE"
13
20
14
18
3
Returns: "DLL"
11
11
12
9
4
Returns: "IMPOSSIBLE"
18
14
19
12
5
Returns: "UDDLL"
16
15
17
13
6
Returns: "IMPOSSIBLE"
18
15
19
13
7
Returns: "UUDDDLL"
11
11
12
10
0
Returns: "IMPOSSIBLE"
19
16
20
15
1
Returns: "IMPOSSIBLE"
15
10
16
9
2
Returns: "DL"
15
19
16
18
3
Returns: "IMPOSSIBLE"
10
16
11
15
4
Returns: "UDDL"
20
14
21
13
5
Returns: "IMPOSSIBLE"
14
13
15
12
6
Returns: "UUDDDL"
14
13
15
12
7
Returns: "IMPOSSIBLE"
17
20
18
20
0
Returns: "IMPOSSIBLE"
14
17
15
17
1
Returns: "D"
17
15
18
15
2
Returns: "IMPOSSIBLE"
20
10
21
10
3
Returns: "UDD"
12
19
13
19
4
Returns: "IMPOSSIBLE"
17
10
18
10
5
Returns: "UUDDD"
10
16
11
16
6
Returns: "IMPOSSIBLE"
17
18
18
18
7
Returns: "UUUDDDD"
17
19
18
20
0
Returns: "IMPOSSIBLE"
14
14
15
15
1
Returns: "IMPOSSIBLE"
11
14
12
15
2
Returns: "DR"
11
12
12
13
3
Returns: "IMPOSSIBLE"
16
15
17
16
4
Returns: "UDDR"
17
16
18
17
5
Returns: "IMPOSSIBLE"
13
18
14
19
6
Returns: "UUDDDR"
19
18
20
19
7
Returns: "IMPOSSIBLE"
14
15
15
17
0
Returns: "IMPOSSIBLE"
18
10
19
12
1
Returns: "IMPOSSIBLE"
19
20
20
22
2
Returns: "IMPOSSIBLE"
16
19
17
21
3
Returns: "DRR"
19
19
20
21
4
Returns: "IMPOSSIBLE"
19
17
20
19
5
Returns: "UDDRR"
19
18
20
20
6
Returns: "IMPOSSIBLE"
12
20
13
22
7
Returns: "UUDDDRR"
16
10
18
8
0
Returns: "IMPOSSIBLE"
12
19
14
17
1
Returns: "IMPOSSIBLE"
12
19
14
17
2
Returns: "IMPOSSIBLE"
11
17
13
15
3
Returns: "IMPOSSIBLE"
16
10
18
8
4
Returns: "DDLL"
13
17
15
15
5
Returns: "IMPOSSIBLE"
12
19
14
17
6
Returns: "UDDDLL"
16
10
18
8
7
Returns: "IMPOSSIBLE"
19
12
21
11
0
Returns: "IMPOSSIBLE"
11
18
13
17
1
Returns: "IMPOSSIBLE"
16
10
18
9
2
Returns: "IMPOSSIBLE"
16
17
18
16
3
Returns: "DDL"
17
20
19
19
4
Returns: "IMPOSSIBLE"
15
11
17
10
5
Returns: "UDDDL"
18
16
20
15
6
Returns: "IMPOSSIBLE"
11
11
13
10
7
Returns: "UUDDDDL"
16
16
18
16
0
Returns: "IMPOSSIBLE"
18
11
20
11
1
Returns: "IMPOSSIBLE"
19
12
21
12
2
Returns: "DD"
20
17
22
17
3
Returns: "IMPOSSIBLE"
17
17
19
17
4
Returns: "UDDD"
19
11
21
11
5
Returns: "IMPOSSIBLE"
16
18
18
18
6
Returns: "UUDDDD"
18
15
20
15
7
Returns: "IMPOSSIBLE"
16
13
18
14
0
Returns: "IMPOSSIBLE"
15
16
17
17
1
Returns: "IMPOSSIBLE"
11
12
13
13
2
Returns: "IMPOSSIBLE"
17
15
19
16
3
Returns: "DDR"
20
20
22
21
4
Returns: "IMPOSSIBLE"
11
14
13
15
5
Returns: "UDDDR"
17
11
19
12
6
Returns: "IMPOSSIBLE"
15
10
17
11
7
Returns: "UUDDDDR"
16
19
18
21
0
Returns: "IMPOSSIBLE"
11
19
13
21
1
Returns: "IMPOSSIBLE"
13
18
15
20
2
Returns: "IMPOSSIBLE"
20
13
22
15
3
Returns: "IMPOSSIBLE"
18
14
20
16
4
Returns: "DDRR"
14
18
16
20
5
Returns: "IMPOSSIBLE"
19
11
21
13
6
Returns: "UDDDRR"
18
10
20
12
7
Returns: "IMPOSSIBLE"
36
92
22
62
712
Returns: "DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUULLLLLLLLLLLLLLLLLLLLLLLLLLLLLL"
30
51
78
60
7
Returns: "IMPOSSIBLE"
75
51
77
30
640
Returns: "IMPOSSIBLE"
70
47
100
13
345
Returns: "IMPOSSIBLE"
8
20
75
13
244
Returns: "UUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDLLLLLLL"
23
10
18
65
172
Returns: "DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUURRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR"
92
21
9
11
128
Returns: "IMPOSSIBLE"
75
50
44
15
984
Returns: "DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUULLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL"
53
37
70
81
224
Returns: "IMPOSSIBLE"
86
44
98
11
656
Returns: "IMPOSSIBLE"
40
13
4
25
830
Returns: "DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUURRRRRRRRRRRR"
71
17
42
11
853
Returns: "DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUULLLLLL"
40
98
91
84
961
Returns: "UUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDLLLLLLLLLLLLLL"
54
64
69
73
770
Returns: "UUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDRRRRRRRRR"
98
87
45
66
531
Returns: "IMPOSSIBLE"
54
81
56
55
692
Returns: "UUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDLLLLLLLLLLLLLLLLLLLLLLLLLL"
52
93
62
2
199
Returns: "UUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL"
41
6
76
54
922
Returns: "IMPOSSIBLE"
12
56
98
74
127
Returns: "IMPOSSIBLE"
12
42
55
94
933
Returns: "UUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR"
7
42
100
96
137
Returns: "IMPOSSIBLE"
85
52
60
94
68
Returns: "IMPOSSIBLE"
60
88
66
15
78
Returns: "IMPOSSIBLE"
25
80
3
69
36
Returns: "IMPOSSIBLE"
41
18
86
20
46
Returns: "IMPOSSIBLE"
9
6
95
77
160
Returns: "IMPOSSIBLE"
5
82
79
85
69
Returns: "IMPOSSIBLE"
32
44
24
71
34
Returns: "IMPOSSIBLE"
47
47
17
25
53
Returns: "IMPOSSIBLE"
78
4
94
38
54
Returns: "UUDDDDDDDDDDDDDDDDDDRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR"
85
38
53
14
56
Returns: "UUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUULLLLLLLLLLLLLLLLLLLLLLLL"
53
44
96
63
59
Returns: "IMPOSSIBLE"
5
92
72
92
71
Returns: "UUDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD"
62
29
34
51
45
Returns: "IMPOSSIBLE"
3
50
24
98
68
Returns: "IMPOSSIBLE"
46
66
11
44
62
Returns: "IMPOSSIBLE"
79
80
43
56
55
Returns: "IMPOSSIBLE"
8
60
34
8
75
Returns: "IMPOSSIBLE"
26
29
54
60
56
Returns: "IMPOSSIBLE"
37
0
14
77
108
Returns: "DDDDUUUUUUUUUUUUUUUUUUUUUUUUUUURRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR"
0
0
5
5
4
Returns: "IMPOSSIBLE"
100
100
0
0
1000
Returns: "DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUULLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLLL"
1
1
1
1
4
Returns: "UUDD"
0
0
10
0
10
Returns: "DDDDDDDDDD"