H. Programming a robot
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

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.

Input

The input has one line with a pair of integers that indicate the starting coordinates, xo and yo, 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, xd and yd.

  • 0 ≤ xo, yo ≤ 5·105
  • 0 ≤ xd, yd ≤ 5·105
Output

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.

Examples
Input
15 2 E
7 9
Output
5
D
D
A 8
D
A 7
Input
0 0 N
0 12
Output
1
A 12