P15623 [ICPC 2022 Jakarta R] Grid Game

给定一个大小为 $N \times M$ 的网格 $A$。行编号从 $1$ 到 $N$，列编号从 $1$ 到 $M$。位于第 $r$ 行、第 $c$ 列的单元格记作 $(r, c)$。 单元格 $(r, c)$ 包含一个整数 $A_{r,c}$，其值可以是 $-1$ 或一个非负整数。如果 $A_{r,c} = -1$，则表示单元格 $(r, c)$ 是**不可通行**的。否则，单元格 $(r, c)$ 是**可通行**的。 两名玩家将在这个网格上轮流进行游戏。在一个回合中，玩家需要执行以下操作： 1. 选择一个写有**正**整数的单元格，玩家从站在该单元格开始。设该起始单元格上的整数为 $x$。 2. 选择一个**非负**整数 $y$，满足 $y < x$。 3. 假设玩家当前站在单元格 $(r, c)$ 上。将 $A_{r,c}$ 的值更新为 $A_{r,c} \oplus x \oplus y$，其中 $\oplus$ 是按位异或运算符。 4. 如果单元格 $(r + 1, c)$ 或单元格 $(r, c + 1)$ 是可通行的，则玩家必须移动到这两个可通行单元格中的一个（由玩家选择）。然后，重复步骤 3。 5. 如果玩家无法再移动，则玩家将走出网格并结束他的回合。 如果一名玩家在他的回合中无法进行游戏（即没有正整数的单元格），则该玩家输掉游戏，对手获胜。 假设双方都采取最优策略，请确定谁将赢得游戏。

输入以两个整数 $N$ $M$（$1 \leq N, M \leq 500$）开始，表示网格 $A$ 的大小。接下来的 $N$ 行，每行包含 $M$ 个整数 $A_{r,c}$（$0 \leq A_{r,c} \leq 10^9$ 或 $A_{r,c} = -1$），表示单元格 $(r, c)$ 中包含的整数。

如果先手玩家获胜，则输出 `first`。如果后手玩家获胜，则输出 `second`。

#### 样例输入/输出 #1 的解释 先手玩家可以从 $(2, 2)$ 开始他的回合，并选择 $y = 0$。然后，他可以沿着写有整数 $3$ 的单元格移动，并将这些单元格更新为 $3 \oplus 3 \oplus 0 = 0$。在先手玩家的回合结束后，网格上不再有正整数的单元格，因此后手玩家无法进行游戏。 #### 样例输入/输出 #2 的解释 先手玩家在第一回合有 $5$ 种可行的选择，如下图所示。每种选择有不同的起始单元格（缩写为 SC）、$y$ 的值以及先手玩家采取的路径。所采取的路径由红色阴影单元格表示。 :::align{center}  ::: 先手玩家为了确保胜利可以采取的最优策略是选项 $1$ 或 $2$。 #### 样例输入/输出 #3 的解释 初始网格中没有正整数的单元格。后手玩家默认获胜。 翻译由 DeepSeek 完成