Arrow Game Winning Strategy

Hansel and Gretel are playing the Arrow Game on an $R\times S$ board. Each cell contains one arrow: $\leftarrow$, $\rightarrow$, $\uparrow$, or $\downarrow$.

The game proceeds as follows:

1. Hansel chooses exactly $K$ cells (which are not in the last column) to color.
2. Gretel then selects any cell in the first column as the starting cell for a robot.
3. The robot is placed on that cell and follows the arrow directions automatically. It stops immediately when it reaches a cell in the last column.

The result is determined by the robot’s path:

• If the robot eventually stops (i.e. reaches the last column in finite time), Hansel wins if and only if the robot passes through exactly one colored cell. Otherwise, Gretel wins.
• If the robot never stops (i.e. gets caught in an infinite loop), Hansel wins.

Note that the robot’s path includes the starting cell, the final cell and all cells in between. It is guaranteed that no arrow points outside the board.

Your task is to decide whether Hansel has a winning strategy – that is, whether there exists a selection of $K$ cells for coloring (only from columns $1$ to $S-1$) such that for every choice of starting cell in the first column, Hansel wins. If a winning strategy exists, output the strategy (i.e. the $K$ cells to be colored). Otherwise, output -1.

inputFormat

The first line contains three integers $R$, $S$, and $K$, where $R$ is the number of rows, $S$ is the number of columns and $K$ is the number of cells to color.

The next $R$ lines each contain a string of $S$ characters. Each character is one of: '', '^', or 'v' — representing the arrows $\leftarrow$, $\rightarrow$, $\uparrow$, and $\downarrow$, respectively.

outputFormat

If Hansel has a winning strategy, output $K$ lines, each containing two integers representing the 1-indexed row and column of a cell to color. If no winning strategy exists, output -1.

sample

1 3 1
>>>

1 1