This is an interactive task.

You're an ant, and not just a regular ant, you're an ant obsessed with kruhology! While most other ants are busy watching the Cup, you're currently on a slice of bread magically floating in the air...

The slice of bread can be imagined as a collection of unit cubes whose upper faces are all in the same plane. Let the total number of faces of the slice of bread be ~n~. All unit cubes are connected. In other words, by moving along the faces of the cubes, one can go from any face to any other face. For any two cubes sharing just one edge, there is another cube which shares a face with both of those cubes.

Currently, you are on some face of some cube and oriented in an unknown way. You don't know anything about the global structure of the slice. You conveniently carry around a marker you stole from high school with which you can leave a tiny mark on each face. You can erase the mark as well! You can repeat any of the following operations ~q~ times:

• K - make a step in your current direction
• L - rotate ~90^{\circ}~ to the left
• D - rotate ~90^{\circ}~ to the right
• X - if the current face has no mark, make one, else remove it

Notice that you can be directed to the edge of the slice and still make a step forwards. In that case, you will end up on a lateral face of a cube. If you make another step, you will end up on the other side of the slice of bread! Because of this, in each moment, you can do any of the four operations.

A hole on a slice of bread is defined as a part of space fully surrounded by cubes. The drawn figure has exactly one hole in the middle. Notice that a hole can contain more than one connected "empty" cube and can be of any shape.

You like holes, so you are really interested in the number of holes in the slice of bread you are on! Try and find out!

Interaction

This is an interactive task. Your task is to make a solution which will calculate the number of holes in a slice of bread. In every moment, you can do one of the four given operations. The grader will output either the number 0 or 1 after you make a step forward. The number 1 means that the face you have just stepped on is already marked, and 0 means the face is unmarked. After outputting an operation and before inputting the grader's response, you should flush the output.

If you do more than ~q~ operations, your solution will be considered incorrect. After at most ~q~ operations you should output the answer in the following format ! g where ~g~ should be the number of holes in the slice of bread.

Constraints

Subtask	Points	Constraints
~1~	~49~	~n \le 40~, ~q = 20\,000~, there is at most one hole in the slice
~2~	~61~	~n \le 200~, ~q = 20\,000~

Please note that the data may not necessarily be the same as the original contest.

Sample Interaction 1

>>> denotes your output. Do not print this out.

>>> X
>>> K
0
>>> L
>>> L
>>> K
1
>>> X
>>> D
>>> D
>>> K
0
>>> ! 1

Explanation for Sample Interaction 1

In the first example, you are somewhere on the slice of bread drawn in the statement. The slice has exactly one hole, and the correct answer is ~1~.

Sample Interaction 2

>>> denotes your output. Do not print this out.

>>> X
>>> K
0
>>> K
0
>>> K
0
>>> K
1
>>> ! 0

Explanation for Sample Interaction 2

In the second example, you are located on a single-unit cube. It has no holes, and therefore the answer is ~0~.