310898: CF1906G. Grid Game 2

G. Grid Game 2time limit per test1 secondmemory limit per test1024 megabytesinputstandard inputoutputstandard output

You are playing "Grid Game 2" with your friend. There is a grid with $10^9$ rows (numbered from $1$ to $10^9$) and $10^9$ columns (numbered from $1$ to $10^9$). The cell at row $r$ and column $c$ is denoted as $(r, c)$.

Each cell can have a colour of either black or white. Initially, there are exactly $N$ black cells (numbered from $1$ to $N$). Black cell $i$ is located at $(R_i, C_i)$. The rest of the cells are white.

You and your friend will alternately take turn playing on this grid, and you are playing in the first turn. In one turn, a player will choose a black cell $(r, c)$, then toggle cells $(r - x, c - y)$ for all $0 \leq x, y < \min(r, c)$. If a cell is toggled, then the cell becomes black if it was a white cell, and the cell becomes white if it was a black cell.

For example, the following illustration shows how the grid changes after a player chooses a black cell $(5, 4)$ in their turn.

A player who is unable to play on their turn, i.e. no remaining black cells, loses the game, and the opposing player wins the game. If you and your friend are playing optimally, determine who will win the game.

Input

The first line consists of an integer $N$ ($1 \le N \le 200\,000$).

Each of the next $N$ lines consists of two integers $R_i$ $C_i$ ($1 \leq R_i, C_i \leq 10^9)$. For $1 \leq i < j \leq N$, $(R_i, C_i) \neq (R_j, C_j)$.

Output

Output FIRST if you will win the game, or SECOND otherwise.

ExamplesInput

2
2 3
2 4

Output

FIRST

Input

1
2 2

Output

SECOND

Input

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

Output

SECOND

Note

Explanation for the sample input/output #1

You can start your move by choosing $(2, 4)$, whose effect was demonstrated in the following illustration.

The remaining black cells are $(1, 3)$ and $(1, 4)$, each of which will only toggle itself when chosen. Whichever your friend chooses on the next move, the you can choose the remaining black cell.

Explanation for the sample input/output #2

You have only one cell to choose, and will toggle cells $(1, 1)$, $(1, 2)$, $(2, 1)$, and $(2, 2)$. Your friend and you will alternately choose the remaining black cells with your friend choosing the last black cell.

题目大意：
你和朋友在玩“网格游戏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)$。如果单元格被切换，那么白色单元格会变成黑色，黑色单元格会变成白色。

如果一个玩家在他的回合无法操作，即没有剩余的黑色单元格，那么该玩家输掉游戏，对方玩家赢得游戏。如果你和你的朋友都采取最优策略，确定谁将赢得游戏。

输入输出数据格式：
输入：
第一行包含一个整数$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”。有一个有$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)$。如果单元格被切换，那么白色单元格会变成黑色，黑色单元格会变成白色。 如果一个玩家在他的回合无法操作，即没有剩余的黑色单元格，那么该玩家输掉游戏，对方玩家赢得游戏。如果你和你的朋友都采取最优策略，确定谁将赢得游戏。 输入输出数据格式： 输入： 第一行包含一个整数$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"。