1 atcoder#ARC103B. [ABC111D] Robot Arms
[ABC111D] Robot Arms
Score : points
Problem Statement
Snuke is introducing a robot arm with the following properties to his factory:
- The robot arm consists of sections and joints. The sections are numbered , , ..., , and the joints are numbered , , ..., . Section connects Joint and Joint . The length of Section is .
- For each section, its mode can be specified individually. There are four modes:
L
,R
,D
andU
. The mode of a section decides the direction of that section. If we consider the factory as a coordinate plane, the position of Joint will be determined as follows (we denote its coordinates as ):- .- If the mode of Section is
L
, . - If the mode of Section is
R
, . - If the mode of Section is
D
, . - If the mode of Section is
U
, .
- If the mode of Section is
Snuke would like to introduce a robot arm so that the position of Joint can be matched with all of the points by properly specifying the modes of the sections. Is this possible? If so, find such a robot arm and how to bring Joint to each point .
Constraints
- All values in input are integers.
Partial Score
- In the test cases worth points, and hold.
Input
Input is given from Standard Input in the following format:
Output
If the condition can be satisfied, follow the following format. If the condition cannot be satisfied, print -1
.
and are the configurations of the robot arm. Refer to the problem statement for what each of them means. Here, and must hold. Also, and must all be integers.
is a string of length that represents the way to bring Joint of the robot arm to point .
The -th character of should be one of the letters L
, R
, D
and U
, representing the mode of Section .
3
-1 0
0 3
2 -1
2
1 2
RL
UU
DR
In the given way to bring Joint of the robot arm to each , the positions of the joints will be as follows:
- To : First, the position of Joint is . As the mode of Section is
R
, the position of Joint is . Then, as the mode of Section isL
, the position of Joint is . - To : $(x_0, y_0) = (0, 0), (x_1, y_1) = (0, 1), (x_2, y_2) = (0, 3)$.
- To : $(x_0, y_0) = (0, 0), (x_1, y_1) = (0, -1), (x_2, y_2) = (2, -1)$.
5
0 0
1 0
2 0
3 0
4 0
-1
2
1 1
1 1
2
1 1
RU
UR
There may be duplicated points among .
3
-7 -3
7 3
-3 -7
5
3 1 4 1 5
LRDUL
RDULR
DULRD