% topic: swarm intelligence
% difficulty: N/A
% usage: creative
% author: Daniel (with Nikola, Cyril, Serge at BOI)

% translation: sam

\bigcaption{Anthill}

{\it Note:} As every year, the creativity task allows you to try your hand at a more extensive, interesting problem. Since we deliberately want to allow many different solutions, it might happen that we will have to slightly modify the rules of the game during the first round. Any changes will be listed at the end of the task description.

\section{The Game}

Ants are highly intelligent animals. They have outstanding skills to organize themselves, allowing them to build huge buildings such as anthills.

In this task, you will help the ants to find their way back to their hill. You will write a program which controls one ant, and therefore only knows the field of vision of one single ant. Using scents, that your ant can secrete, you can communicate with other ants of your population, e.g. to explain them how to get to the hill or to advise them of other things.

This is an interactive task. This means that at every step, you get a little map representing the environment of your ant, and after that, you can decide what move you want to do.

Since your ant population consists of several ants, your program will be running simultaneously in several independent instances. Your programs are not allowed to communicate directly. The only legal way of interaction is to put scents onto the map.

The goal of the game is that your ants find their own hill as fast as possible.


\section{Rules}

The game is played on a torus, of which you know the size. You can also imagine the playing field as a rectangle where the opposite sides are connected to each other. This means that if an ant leaves the playing field at the north border, then it enters the field on the south-most tile in the same column, and analogously for west and east.

However, your ant never knows its absolute coordinates. There are no obstacles in the world of the ants, only other ants and the hills of the ant populations.


\subsection{Beginning of the game}

At the beginning of the game, you read seven integers and a lower-case letter on one single line: \verb|W H K N Z V S I|

They describe the following:
\begin{itemize}
\item $W$ and $H$: the size of the playing field (a rectangle of width $W$ and height $H$, with $1 \le W,H \le 1000$)
\item $K$: the conflict constant (explanation see below)
\item $N$: the number of ants per population
\item $Z$: the number of ants which must reach the hill for the game to be finished, i.e. $1 \le Z \le N$
\item $V$: the number of ant populations on the playing field, , $1 \leq V \leq 26$
\item $S$: the side length of the square representing your anthill
\item $I$: the identification letter of your ant population (a lower case letter from 'a' and 'z')
\end{itemize}

{\it Example:}
\verb|10 20 10 15 13 4 1 b|

The game is played on a rectangle of width 10 and height 20. The conflict constant equals 10. Each of the 4 ant populations consists of 15 ants, and all ants controlled by you are marked with a 'b'. As soon as a population has 13 ants in the hill, they win.
Every anthill consists of one single tile (a 1x1 square).

At the beginning of the game, all ants are randomly distributed on the playing field.


\subsection{One Step}
\caption{Input}

In every step, the input contains first one line describing the last move of your ant with a single letter or with a single letter followed by two integers (see below):

\begin{itemize}
\item \verb|N|, \verb|E|, \verb|S| or \verb|W|: Your ant moved by one tile in the corresponding direction (north, east, south or west).

\item \verb|H|: Your ant stayed on the same tile, either because you wanted it, or because there was a conflict at the last move.

\item \verb|M|: Your ant has put a scent on the map.

\item \verb|J a b|: Because your ant has not been moving during $K$ steps, your ant was bored and has moved by $a$ tiles horizontally and by $b$ tiles vertically. $a > 0$ means that your ant moved east, $a < 0$ west, $b > 0$ north and $b < 0$ south. So, this corresponds to a Cartesian coordinate system.

\end{itemize}

In the very first step, this line is one single letter \verb|H|.

Then, your ant gets two 7x7 maps of its environment, facing north, in the following format:

The first map consists of 7 lines of 7 characters each, and the characters represent the following:
\begin{itemize}

\item '$.$': a free tile

\item lower-case letter '$x$': an ant of population $x$

\item upper-case letter '$X$': the anthill of population $x$
\end{itemize}

The second map, starting on a new line, consists of 7 lines of 7 integers each (separated by a space), and the numbers represent the following:

Number $m$: $0 \le m \le 255$: a scent with value $m$, or if the concerned tile is an anthill, then $m$ is the number of ants in this hill. All tiles are initiated with scent 0 at first.

{\it Sample input:}
\inputdef
W
...a...
....CC.
b...CC.
...d...
.c.....
.....EE
.FF..EE
0 0 33 0 0 0 0
0 0 0 0 2 2 0
0 0 0 0 2 2 0
0 0 44 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 1 1
0 0 0 0 55 1 1
\enddef

{\it Explanation:}

In the last step, your ant moved one tile to the west. Your ant sees one ant of populations $a$, $b$, $c$, $d$ each, and the hills of populations $c$, $e$, and $f$. Further, it sees tiles with scents 33, 44 and 55.

In hill $C$, there are two ants of population $c$, in hill $E$, there is one ant and hill $F$ is empty. Every hill is a 2x2 square, so the value of $S$ is 2.
Note that only one half of hill F is on the map.

Your ant is always in the middle, so here, you are an ant of population $d$.

If your ant is in the hill, the first map contains the character of the hill.

\caption{Output}
Output one line describing what your ant should do in this step. You have the following possibilities:
\begin{itemize}
\item Stay on the same tile: \verb|H|
\item move 1 tile to the north: \verb|N|
\item move 1 tile to the east: \verb|E|
\item move 1 tile to the south: \verb|S|
\item move 1 tile to the west: \verb|W|
\item put a scent of value $m$ ($0 \le m \le 255$): \verb|M m|
\end{itemize}


\subsection{Detail Specifications}
\begin{itemize}
\item If your ant puts a scent on the map, it stays on the same tile.
You cannot put scents on the anthill. The hill has an automatic scent number, which is the number of ants in the hill at the beginning of the step.

\item On every tile, there can be only one ant at the same time.

\item If several ants want to move onto the same tile in the same step, the move is not executed, and the concerned ants get an $H$ as a feedback in the next step. If your ant wants to move onto an opponent's hill, it does not move and also gets an $H$.

\item If an ant wants to move onto an ant secreting a scent, it does not move, but the scent is put.

\item If two ants both move on the tile of the other ant in the same step, i.e., if they swap their positions, this works perfectly.

\item If an ant puts a scent on a tile, this scent is conserved until the next ant puts another scent on this tile. Scents are visible and overwriteable for all ants, not only for those of your own population. So, think of a way how to make sure you interpret the scents correctly, without being taken by ``wrong'' scents of other ants.

\item In order to avoid that ants block each other, we demand that they move from time to time. In practice, this means that if your ant stays on the same tile during $K$ steps, then your ant automatically jumps to a randomly chosen tile in its environment (a tile with distance $\le 10$ to the old position).
Note that the ant will be put onto an arbitrary tile in its close environment, even if it was not able to leave its old position (e.g. because it was completely surrounded by other ants).

\item On the anthill of the own population, there can be any number of ants of the corresponding population for as much time as they want, and they can also stay on the same tile as long as they want to. If an ant has entered its hill, it is allowed to leave it again (if it wants to do so).
\end{itemize}

\section{End of Game}
Your ant population has solved the task successfully as soon as $Z$ out of the $N$ ants are in the anthill.

As soon as $Z$ of your ants have entered the hill, \underline{all} your $N$ programs get two maps consisting only of dots (first map) or only of zeroes (second map). Then, your program should terminate correctly and free all allocated resources, otherwise, it will be terminated by the server.

You can use your own position as an indicator, i.e., the run time of your ant instance is over as soon as the fourth character in the fourth line of the first map is a dot.

\section{Tips}
For interactive tasks, it is important that you flush the input/output buffer after every step. Use the following commands:

C/C++: \verb|fflush(stdout);|

C++: \verb|cout << flush;|

Pascal: \verb|flush(output);|

Further, when reading input, it is important that your program does not wait for more characters than the server gives you as input. Especially spaces or line breaks in the format string in C are a common cause of error. For instance, if you read the last variable of the input with \verb|scanf("%d ", &x);|, the scanf function waits for the next character which is not a space or a newline. However, you will get such a character only after you have announced your move. So, your program would block here.


\section{Server and Visualization}

During the first round, we will provide a server program, which you can use to let your own program compete against your and other programs, as well as a visualization, which animates simulated games. You will find those on this website, and since they are continuously developed, it is worth having a look at the website from time to time.

\section{Grading}
Since there is obviously no perfect solution and in order to motivate you even more for this creativity task, the grading scheme for the creativity task is different than for the other tasks. You get:

\begin{itemize}

\item 50\% of the points for a program which plays the game correctly, i.e. which respects all the rules and plays at least as well as the sample bots. Important: You are not allowed to simply copy and submit the code of the sample bots. However, you are allowed and encouraged to use them as instructions on how to correctly do the input/output in your programming language. To get the 50\% of the points, we explicitly do not ask you to lead your ants to the hill in a more clever way than by simply letting them wandering around. But to win the tournament, of course, it is necessary that your ants act as intelligently as possible.
   
\item the remaining 50\% of the points are awarded according to the result at the ants tournament at the SOI day.
\end{itemize}

