404391: GYM101492 H Programming a robot

The last edition of the world robot conference took place in China last year, the most recent innovations on robots were on display. Those ranged from machines able to make people's portraits to robots that can play soccer.

We want to program a robot, but a less sophisticated one. It takes only two commands:

• Walk(k): takes k steps forward
• TurnRight(): turns 90 degrees to its right.

At first, we just want to program this robot's movements. For that, we need you to print a sequence of commands to complete the following action: given the Cartesian coordinates of start and destination, and the initial direction the robot initially points to (North, South, East, or West), print a sequence of commands that takes the robot from its starting position to its destination.

Since we are always concerned about efficiency, we wish the sequence to be as small as possible.

The input has one line with a pair of integers that indicate the starting coordinates, x_o and y_o, followed by a character that indicates a direction (N for North, S for South, E for East, or O for West). The next line contains a pair of integers indicating the destination coordinates, x_d and y_d.

• 0 ≤ x_o, y_o ≤ 5·10⁵
• 0 ≤ x_d, y_d ≤ 5·10⁵

In the first line, print the smallest size of a sequence of commands that take the robot from start to destination. In the next lines, print one of these sequences, one command per line. For the command Walk((k)), print "A k" (without the double quotes). For the command TurnRight(), print "D".

If there is more than one sequence of instructions that work, any one of them will be accepted.

15 2 E
7 9

5
D
D
A 8
D
A 7

0 0 N
0 12

1
A 12