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