====== Creativity Task: Multisnake ======
{{ soi:aufgaben:gordianknot.jpg}}
<box 25% left orange|Eckdaten>
Zuständig: Daniel, Sämi, Silvan, Shino, Timon\\
interaktive Aufgabe\\
[[soi:aufgaben:msnake:de|deutsch]],
</box>
<box 25% left green|Technische Informationen>
[[soi:aufgaben:msnake:notizen|Notizen]] \\
[[soi:aufgaben:msnake:eingabe|Eingabedateien und -generator]] \\
[[soi:aufgaben:msnake:loesung|Musterlösung(en)]] 
</box>





===== Introduction =====
Mouse Stofl and his friends enjoy playing Multisnake. Multisnake is an extended clone of the classic Snake game. Multisnake supports Multiplayer matches for up to 8 players. Unfortunately, Mouse Stofl is the worst Snake player: He loses every game. This is very frustrating.

One day, he came up with the idea to create a computer program which could replace his inputs and win the game. There are whispers that //you// are a very skilled programmer and therefore Stofl is asking for your assistance.

===== Multisnake =====
Multisnake is played on a rectangular tiled map of size WxH and there are 2, 4 or 8 players on a map that compete each other. Each player controls a snake that occupies a number of adjacent tiles. The map is repetitive: Players who leave the map enter it on the opposite side.

A game is played in frames (turns). In each turn, all players move simultaneously following this set of rules:
  - Snakes move by avancing their head and tail by one tile per turn. If a snake attempts to enter a tile which is occupied it does not move in that turn and dies. If multiple snakes attempt to enter the same tile, they die after performing the move. Dead snakes stay on the map. Note that as all snakes move at the same time, a snake may enter a tile that is left by the tail of another snake in the same turn.
  - There are tiles that contain + or - signs. When a snake enters such a tile, the sign is consumed by the snake and the snake grows (+) or shrinks (-) by one tile. Growth and shrinking are performed by not moving the tail or moving the tail by two tiles respectively. If a snake shrinks to length zero, it dies.
  - To enforce termination of the game, all snakes grow by one each T turns, where T is a small positive integer. A snake can grow by at most one tile per turn. Consequently, consumed + signs are ignored and a snake that consumes a - sign does not grow in these turns. 
  - The last player whose snake is still alive wins the game. If all snakes that are left die at the same turn, the game is a tie.

===== Server Interaction =====
All interaction will be text-mode based. This is an interactive task, therefore it is crucial that you remember to flush standard output.

At the beginning of the game, the server supplies your program with information about the game. Read five integers W, H, N (number of players), M (your number) and T from standard input.

At the beginning of each move, read the map from standard input. It consists of H lines, each containing W characters. The meaning of each character is explained in the table below:

^ Character     ^ ANSI-Value     ^ Meaning                                                                                    ^
| ''A,B,C...''  |  65, 66, 67... | Snakes' heads. Your head's ANSI-Value is given by 64+M.                                    |
| ''@''         |             64 | Dead snakes' heads                                                                         |
| ''#''         |             35 | An impenetrable tile                                                                       |
| ''v''         |            118 | Part of a snake's body, when the snake's head was on this tile, the snake moved down       |
| ''<''         |             60 | Part of a snake's body, when the snake's head was on this tile, the snake moved left       |
| ''>''         |             62 | Part of a snake's body, when the snake's head was on this tile, the snake moved right      |
| ''^''         |             94 | Part of a snake's body, when the snake's head was on this tile, the snake moved up         |
| ''.''         |             46 | Free tile                                                                                  |
| ''+''         |             43 | + sign, increases snake's length by 1                                                  |
| ''-''         |             45 | - sign, decreases snake's length by 1                                                  |
There are no other characters in the map representation.

After reading the input, you must output exactly one line containing a char ('^', '>', 'v' or '<'), which indicates in which direction the snake should move. Your program is terminated automatically if your snake dies, the game ends or you output an invalid line.

===== Constraints =====
  * 5 <= W,H <= 150
  * N = 2 //OR// N = 4 //OR// N = 8
  * 1 <= M <= N
  * 1 <= T <= 25



===== Example map =====
This is a map at an arbitrary turn in the format the server will provide it to your program.
<code>
##########.^.....^##########
#....>>>>>>^.....^<...>>>v.#
#.......-..........-.....v.#
>>>>>>>>>>>>>>>B...+.....>>>
#...................v......#
#...+..A<.########..v..+...#
##......^<<<.....>>>@.....##
###....-...^.....^..-....###
</code>
The map contains four snakes two of which entered the same tile in the same turn and died. Note how snakes that left the map entered it again on the opposite side.


===== Remarks =====
  - You can use the testing server to evaluate a number of programs locally. The fully working random player is implemented in multiple programming languages to provide you a starting point.
  - Maps used in the tournament will be symmetric (the same for all players).
<html><script>toggleToc();</script></html>