题目描述

Given a grid $A$ of size $N \times M$. Each row is numbered from $1$ to $N$, and each column is numbered from $1$ to $M$. The cell at row $r$ and column $c$ is denoted as $(r, c)$.

Cell $(r, c)$ contains an integer $A_{r,c}$, which can be either $-1$ or a non-negative integer. If $A_{r,c} = -1$, that means cell $(r, c)$ is impassable. Otherwise, cell $(r, c)$ is passable.

Two players will alternately take turns playing on this grid. In one turn, a player will do the following.

1. Choose a cell with positive integer on it, and the player starts standing on that cell. Let $x$ be the integer at this starting cell.
2. Choose a non-negative integer $y$ such that $y < x$.
3. Suppose that the player is standing on cell $(r, c)$. Update the value of $A_{r,c}$ to $A_{r,c} \oplus x \oplus y$, where $\oplus$ is the bitwise operator XOR.
4. If either cell $(r + 1, c)$ or cell $(r, c + 1)$ is passable, the player must move to either passable cell of the player's choosing. Then, repeat from step 3.
5. If the player is no longer able to move, the player will step outside of the grid and end his turn.

A player who is unable to play on his turn (i.e. no positive integer on his turn) loses the game, and the opposing player wins the game.

If both players play optimally, determine who will win the game.

输入格式

Input begins with two integers $N$ $M$ ($1 \leq N, M \leq 500$) representing the size of grid $A$. Each of the next $N$ lines contains $M$ integers $A_{r,c}$ ($0 \leq A_{r,c} \leq 10^9$ or $A_{r,c} = -1$) representing the integer contained in cell $(r, c)$.

输出格式

Input begins with two integers $N$ $M$ ($1 \leq N, M \leq 500$) representing the size of grid $A$. Each of the next $N$ lines contains $M$ integers $A_{r,c}$ ($0 \leq A_{r,c} \leq 10^9$ or $A_{r,c} = -1$) representing the integer contained in cell $(r, c)$.

5 6
0 0 0 0 0 0
0 3 3 0 0 0
0 0 3 -1 0 0
0 0 3 3 3 3
0 0 -1 -1 -1 -1

first

2 2
1 1
2 -1

first

1 1
-1

second

提示

Explanation for the sample input/output #1

The first player can start his turn from $(2, 2)$ and choose $y = 0$. Then, he can keep following the cells with integer $3$ and update those cells to $3 \oplus 3 \oplus 0 = 0$. After the first turn, there is no positive integer on the grids, thus the second player is unable to play.

Explanation for the sample input/output #2

There are $5$ options that can be made by the first player during the first turn, as shown in the following illustration. Each option has different starting cell (abbreviated as SC), the value of $y$, and the path taken by the first player. The taken paths are indicated by the red shaded cells.

:::align{center} :::

The optimal moves for the first player to guarantee his win is either option $1$ or $2$.

Explanation for the sample input/output #3

The initial grid has no positive integer cell. The second player wins the game by default.