2023-2024 ICPC, Asia Jakarta Regional Contest (Online Mirror, Unrated, ICPC Rules, Teams Preferred) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

games

number theory

*2900

No tag edit access

The problem statement has recently been changed. View the changes.

×
G. Grid Game 2

time limit per test

1 secondmemory limit per test

1024 megabytesinput

standard inputoutput

standard outputYou 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.

Examples

Input

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.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/23/2024 22:21:04 (j1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|