Grid Game

A grid $A$ of size $N \times M$ is given. Rows are numbered 1 to $N$ from top to bottom, and columns are numbered 1 to $M$ from left to right. Cell $(r, c)$ is the cell at row $r$ and column $c$.

Each cell $(r, c)$ holds either $-1$ or a non-negative integer $A_{r,c}$. If $A_{r,c} = -1$, the cell is impassable. Otherwise, the cell is passable.

Two players take turns on this grid. On a turn, a player does the following.

1. Chooses a cell with a positive integer and stands on it. Let $x$ be the integer on this starting cell.
2. Chooses a non-negative integer $y$ with $y < x$.
3. While standing on cell $(r, c)$, replaces $A_{r,c}$ with $A_{r,c} \oplus x \oplus y$, where $\oplus$ is the bitwise XOR.
4. If cell $(r+1, c)$ or cell $(r, c+1)$ is passable, the player must move to one of the passable cells of their choice, then repeat from step 3.
5. If the player cannot move, the player leaves the grid and the turn ends.

A player who cannot play on their turn, because no cell holds a positive integer, loses, and the other player wins.

Assuming both players play optimally, determine who wins.

The first line contains two integers $N$ and $M$ ($1 \le N, M \le 500$). Each of the next $N$ lines contains $M$ integers $A_{r,c}$ ($0 \le A_{r,c} \le 10^9$ or $A_{r,c} = -1$).

If the first player wins, print first on a single line. Otherwise, print second on a single line.