← 返回题目列表

Codeforces · 277/C

C. 游戏

中文机器翻译题面 查看原题

两名玩家玩以下游戏。最初,玩家有一把刀和一张矩形纸,纸被分成单位大小的相等的正方形网格单元。玩家轮流走棋,不能走棋的玩家失败。一步操作中,玩家可以拿起刀沿着网格线的任意一段(不一定是从边界到边界)切割纸张。纸张至少接触刀一次的部分被视为被切割。有一个限制不让游戏变成无限循环:每一步都要切纸,即刀必须接触到纸上之前没有切过的部分。

显然,当整张纸被切成 1 × 1 块时,游戏结束。游戏过程中,棋子不得移动。也禁止沿边界砍伐。每个切割末端的坐标必须是整数。

给你一张 n × m 的纸,有人已经在那里做了 k 次切割。您的任务是确定如果玩家开始在这张表上玩,谁将获胜。您可以认为两名球员都发挥得很好。如果第一个玩家获胜,您还需要找到获胜的第一步。

输入

第一行包含三个整数 n、m、k (1 ≤ n, m ≤ 109, 0 ≤ k ≤ 105) — 纸张的尺寸和切割次数。然后是 k 行,每行包含 4 个整数 xbi、ybi、xei、yei (0 ≤ xbi, xei ≤ n, 0 ≤ ybi, yei ≤ m) — 现有切口末端的坐标。

保证每次切割都具有非零长度、垂直或水平且不沿着纸张边框。

切口可能相交、重叠,甚至相同。也就是说,不能保证在任何正确的游戏中都获得了削减。

输出

如果第二个玩家获胜,则打印“SECOND”。否则,在第一行打印“FIRST”,在第二行打印第一个玩家的任何获胜动作(切端的坐标,按照输入格式打印它们)。

示例

输入 #1

2 1 0

输出 #1

FIRST
1 0 1 1

输入 #2

2 2 4
0 1 2 1
0 1 2 1
1 2 1 0
1 1 1 2

输出 #2

SECOND