F. Follow the LIDAR
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The company "Bailes S.A." is interested in making a new domestic cleaning robot. As there is very strong competition in this sector, it has decided to make a robot that has something new and has decided to incorporate a Lidar (a sensor that measures distances by laser). Although, as Lidar sensors are quite expensive, he has opted for a single beam Lidar that allows him to measure the free distance in front of the robot. It has done very well, has already built it and is eager to test it, so it has contacted you to make a software prototype.

Your program must control the movement of the robot on a map defined by a grid of cells using 3 basic commands: move forward, turn left and turn right. When moving forward, it only advances a single cell. The turns are 90 degrees. Each time one of these commands is executed, the number of free cells in front of the robot is received. Each cell of the grid can only be free or occupied. The robot cannot leave the grid and, in fact, the measurement of the number of free cells will be zero if measured from the boundary and outwards.

The robot always starts in the cell at the lower left boundary of the grid and must reach the cell at the opposite end, i.e., if the grid has size $$$N \times N$$$ and we take the lower left cell as the cell whose coordinates are $$$(1,1)$$$, the destination would be the cell whose coordinates are $$$(N,N)$$$. The robot always starts oriented upward, i.e., if its first move is a forward move then it would move to the cell $$$(1,2)$$$. It is guaranteed that $$$N$$$ is at most $$$20$$$.

It is not necessary to find the optimal solution, that is, solutions where the path can be longer than optimal are admitted, but due to battery constraints, the forward movements are limited to $$$4 \cdot N^2$$$. Of course, the solution is not unique, the robot can go through many different paths, in the end it doesn't matter, the important thing is that it cleans.

A possible cell map is shown in the figure. The coordinates of the start and end cell are shown, as well as the coordinates of a couple of additional cells. Cells with an "X" are not free. A "layer" of cells outside the grid, also marked with an "X", is also shown.

Input

The entry consists of a single test case.

On the first line there is a number $$$N$$$, which indicates the size in cells of the problem's grid. Next, you can read, on one line, the number of free cells initially in front of the robot, a positive integer between $$$0$$$ and $$$N-1$$$.

Then, each time the program produces an output (a movement command), the number of free cells in front of the robot will be written on a new line, or END if the robot has reached its destination, that is, if it has reached the cell of coordinates $$$(N, N)$$$.

If the robot is placed on the edge of the grid and facing outward the number of free cells will be $$$0$$$.

Output

Commands are coded with three letters, "A" for "forward" ("Avanzar" in Spanish), "D" for "turn right" ("Derecha" in Spanish) and "I" for "turn left" ("Izquierda" in Spanish). They must be written without quotation marks and a newline must be written after the command. Immediately after writing the command you can read the number of free cells.

If the command to move forward is given and the robot cannot do so because there is no free cell, a wrong result will be automatically produced (Wrong Answer).

Remember that it is convenient to flush the output channel. In C/C++ this is done with: fflush(stdout);, in Java with System.out.fflush(); and in Python with print([...], flush=True);.

Example
Input
5
4
3
2
1
0
2
1
0
2
1
0
2
1
0
2
1
0
4
3
2
1
0
4
3
2
1
END
Output
A
A
A
A
D
A
A
D
A
A
D
A
A
I
A
A
I
A
A
A
A
I
A
A
A
A
Note

The sequence in which the input/output occurs for the first steps is: the 5 ($$$N$$$) and the 4 (free cells) are written to the input, the program then writes A (advance), and immediately afterwards it will have the $$$3$$$ in the input.

  • The example output corresponds to the diagram in the figure.
  • Important: The solution shown as output has been done manually knowing the cell map. It cannot be used as a basis for developing the algorithm.
  • The algorithm has a limit number of forward movements, but there is no limit for turns.
  • Of course, the usual time limit does exist and it overlaps the forward movements limit.
  • An example about turns: if the robot is pointing up (increasing "y" coordinates) and turns to the right, it remains pointing to the right (increasing "x" coordinates) and respectively if it turns to the left it remains pointing to the left (decreasing "x" coordinates).