bee 1525 - Gruntz

Rafael liked a game so much when he was a child, that he decided to draw a map with the characteristics of that game and see if he could complete it.

The map consists of N lines and M columns, that divide the map in a grid of N * M cells. Each of these cells, with exception of the middle cell, contain an arrow drawn on it, that points to one of four directions – Left, Up, Right or Down.

The goal of the game is to position the character at any of the cells that constitutes the border of the map, and make him go to the middle of map, marked with a x. The rules to move in the game follow the arrows logic: The character can only move at the direction that the arrow points.

In other words, if the character is at the cell [x, y] (line x, column y), and at that cell there is an arrow pointing to the right, the only cell he can go from there will be the cell [x, y+1], if it is on the limits of the map (otherwise, he will leave the map, and the game is lost).

To make it easier, Rafael decided that he could make K arrow inversions. When you invert an arrow, it now points to the opposite direction from which it pointed previously. In other words, if it pointed to the Right, it will now point to the Left, and vice versa. The same works for Up and Down.

Rafael now asked your help: Is it possible to position the character at one of the map borders, and make him walk to the middle cell, making at most K arrow inversions?

Input

There will be several test cases. Each test cases starts with three integers N, M and K (3 ≤ N, M < 100, 0 ≤ K ≤ 100, N and M are odds), representing, respectively, the amount of lines and columns of the map, and the maximum number of allowed inversions.

Following there will be N lines, each containing M characteres, that will represent the map Rafael drew. The character at the i-th line and j-th column indicates that at the cell [i, j] of the map there is:

'>' – An arrow pointing to the Right.
'<' – An arrow pointing to the Left.
'^' – An arrow pointing Up.
'v' – An arrow pointing Down.
'x' – The destination cell (which is always in the middle of the map).

The last test case is indicated when N = M = K = 0, which should not be processed.

Output

For each test case print one line, containing the word “Sim” if it is possible to position the character at one of the map borders in a way that he can walk to the destionation cell, making at most K inversions, or “Nao” otherwise.

Sample Input	Sample Output
5 5 0 >>v<< >>v<< >>x<< >>^<< >>^<< 5 5 1 >>v<< ^^^>> ^^x^^ vvv>> >>^<< 0 0 0	Sim Sim