题目描述

你和你的朋友正在玩“Grid Game 2”。有一个 $10^9$ 行（编号从 $1$ 到 $10^9$）和 $10^9$ 列（编号从 $1$ 到 $10^9$）的网格。第 $r$ 行第 $c$ 列的格子记作 $(r, c)$。

每个格子可以是黑色或白色。初始时，恰好有 $N$ 个黑色格子（编号从 $1$ 到 $N$）。第 $i$ 个黑色格子位于 $(R_i, C_i)$。其余格子都是白色。

你和你的朋友轮流在这个网格上进行操作，你先手。在每一回合，玩家需要选择一个黑色格子 $(r, c)$，然后对所有满足 $0 \leq x, y < \min(r, c)$ 的格子 $(r - x, c - y)$ 进行翻转操作。如果一个格子被翻转，那么如果它原本是白色就变成黑色，原本是黑色就变成白色。

例如，下图展示了玩家在自己的回合选择黑色格子 $(5, 4)$ 后，网格的变化情况。

:::align{center} :::

如果某位玩家在自己的回合无法选择黑色格子（即没有剩余的黑色格子），则该玩家输掉游戏，对方获胜。如果你和你的朋友都采取最优策略，判断谁将赢得游戏。

输入格式

第一行包含一个整数 $N$（$1 \le N \le 200\,000$）。

接下来的 $N$ 行，每行包含两个整数 $R_i$ 和 $C_i$（$1 \leq R_i, C_i \leq 10^9$）。对于 $1 \leq i < j \leq N$，有 $(R_i, C_i) \neq (R_j, C_j)$。

输出格式

如果你能赢得游戏，输出 FIRST；否则输出 SECOND。

2
2 3
2 4

FIRST

1
2 2

SECOND

13
1 1
1 4
1 5
2 1
2 4
2 5
4 1
4 2
4 4
5 1
5 2
5 4
5 5

SECOND

提示

样例输入输出 #1 说明

你可以先选择 $(2, 4)$，其效果如下图所示。

:::align{center} :::

剩下的黑色格子是 $(1, 3)$ 和 $(1, 4)$，每次选择时只会翻转自身。无论你的朋友下一步选择哪一个，你都可以选择剩下的黑色格子。

样例输入输出 #2 说明

你只有一个格子可选，将会翻转 $(1, 1)$、$(1, 2)$、$(2, 1)$ 和 $(2, 2)$。你和你的朋友轮流选择剩下的黑色格子，你的朋友会选择最后一个黑色格子。

由 ChatGPT 4.1 翻译