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:
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, 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.
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.
## 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.
[samples]
**Definitions**
Let $ T \in \mathbb{Z} $ be the number of test cases.
For each test case $ k \in \{1, \dots, T\} $:
- $ n_k \in \mathbb{Z} $: number of digits ($1 \leq n_k \leq 10^6$)
- $ s_k \in \mathbb{Z} $: required sum of digits ($1 \leq s_k \leq 9 \times 10^6$)
Let $ P(n, s) $ be the set of $ n $-digit palindromic numbers whose digits sum to $ s $.
**Constraints**
1. $ 1 \leq T \leq 500 $
2. For each test case $ k $:
- $ 1 \leq n_k \leq 10^6 $
- $ 1 \leq s_k \leq 9 \times 10^6 $
- The first digit of the palindrome must be in $ \{1, \dots, 9\} $ (no leading zeros)
**Objective**
For each test case $ k $, find:
$$
\max P(n_k, s_k)
$$
if $ P(n_k, s_k) \neq \emptyset $, otherwise output $ -1 $.