Background

This is an interactive problem.

Problem Description

You are an ant, and you are currently on a piece of bread floating in the air.

The bread can be seen as a 3D shape made of several cubes. This shape has height at most one cube (i.e., there is at most one layer in the vertical direction), and it is connected.

The left image is the first sample, and the right image is an invalid example (not connected).

We denote that the 3D shape formed by these cubes has $n$ faces. You are currently on one cell of one face, facing an unknown direction. You can perform $q$ operations. In each operation, you can:

• $\texttt{K}$: move one cell forward in the direction you are facing;
• $\texttt{L}$: turn left by $90\degree$;
• $\texttt{D}$: turn right by $90\degree$;
• $\texttt{X}$: place / remove a marker on the current cell.

Note: When you reach an edge, if you continue moving forward, you will move onto another face. Therefore, you can walk any number of steps in any direction.

A hole in the cube is defined as a part of space that is completely surrounded by cubes.

You like holes very much, so you want to find the number of holes in this cube.

Input Format

This is an interactive problem. You need to output the number of holes on the bread. You may send one operation to the interactive library, and the library will return a value. A return value of $0$ means there is currently no marker on this cell, and $1$ means there is. If your number of operations exceeds $q$, your answer will be considered incorrect. If you have found the answer, output ! g, where $g$ means you found $g$ holes on the bread.

0


1



0

X
K

L
L
K

X
D
D
K

! 1

0

0

0

1

X
K

K

K

K

! 0

Hint

Translated by ChatGPT 5