Gomoku Grid Analysis

In this problem, zyl and "she" are playing a game similar to Gomoku on an n × m grid. The grid is represented by n strings each of length m consisting only of the characters ~, *, and $.

The meaning of the characters is as follows:

• ~ indicates an empty cell;
• * indicates that "she" has placed a piece in that cell;
• $ indicates that zyl has placed a piece in that cell.

"She" always plays first, and the two players alternate their moves. The game ends if any player manages to form an unbroken line of exactly five of their own pieces in one of the following directions:

• a horizontal line (same row),
• a vertical line (same column),
• a diagonal line (both the main diagonal and the anti-diagonal, which are at 45° angles).

Your task is to analyze the current board configuration. If one of the players has already won (i.e. has five consecutive pieces in any of the allowed directions), output the winner. Otherwise, determine whose turn it is to play next.

Note: Since "she" always starts first, if the number of * pieces equals the number of $ pieces then it is "she"'s turn; if there is one more * than $, it is zyl's turn.

All formulas are formatted in LaTeX.

For example, a win is declared if there exists a sequence of five identical non-empty symbols in any of the following directions:

• Horizontal: $$(i, j), (i, j+1), \dots, (i, j+4)$$
• Vertical: $$(i, j), (i+1, j), \dots, (i+4, j)$$
• Main diagonal: $$(i, j), (i+1, j+1), \dots, (i+4, j+4)$$
• Anti-diagonal: $$(i, j), (i+1, j-1), \dots, (i+4, j-4)$$

inputFormat

The input is given as follows:

n m
s1
s2
...
sn

Here, n and m are two integers representing the number of rows and columns of the grid respectively, and each si is a string of length m containing only the characters ~, *, or $.

outputFormat

If a player has already won (i.e. obtained 5 consecutive pieces in an allowed direction), output the winner: output she if "she" (denoted by *) is the winner, or zyl if zyl (denoted by $) is the winner. Otherwise, output the name of the player whose turn is next. Remember that if the counts of * and $ are equal, then it is "she"’s turn; otherwise, if there is one more * than $, then it is zyl’s turn.

sample

5 5
*****
~~~~~
~~~~~
~~~~~
~~~~~

she