给定一个由小写英文字母组成的 n × n 表 T。如果表包含与给定字符串相对应的正确路径,我们将认为某些字符串是好的。换句话说,好的字符串就是我们从表格的左上单元格向右下移动所能得到的所有字符串。这是正确路径的正式定义:
考虑表的行从上到下从 1 到 n 编号,表的列从左到右从 1 到 n 编号。单元格(r,c)是表T的第r行第c列的单元格。该单元格对应于字母 Tr, c。
长度为 k 的路径是一系列表格单元格 [(r1, c1), (r2, c2), ..., (rk, ck)]。以下路径是正确的:
1、只有一条长度为1的正确路径,即由单个单元格组成:[(1, 1)];
2. 假设 [(r1, c1), ..., (rm, cm)] 是长度为 m 的正确路径,则路径 [(r1, c1), ..., (rm, cm), (rm + 1, cm)] 和[(r1, c1), ..., (rm, cm), (rm, cm + 1)] 是长度为 m + 1 的正确路径。
我们应该假设路径 [(r1, c1), (r2, c2), ..., (rk, ck)] 对应于长度为 k 的字符串:Tr1, c1 + Tr2, c2 + ... + Trk, ck。
两个玩家玩以下游戏:最初他们有一个空字符串。然后玩家轮流在字符串末尾添加一个字母。每次移动(添加一个新字母)后,所得的字符串必须是好的。游戏在 2n - 1 回合后结束。玩家通过以下情况获胜:
1. 如果结果字符串中字母“a”的数量严格多于字母“b”,则第一个玩家获胜;
2. 如果结果字符串中的字母“b”严格多于字母“a”,则第二个玩家获胜;
3. 如果生成的字符串具有相同数量的字母“a”和“b”,则玩家以平局结束游戏。
您的任务是确定游戏结果,前提是两名玩家都发挥最佳。
输入
第一行包含单个数字 n (1 ≤ n ≤ 20)。
接下来的 n 行每行包含 n 个小写英文字母 — 表 T。
输出
在单行中打印字符串“FIRST”,如果第一个玩家获胜,“SECOND”,如果第二个玩家获胜,“DRAW”,如果游戏以平局结束。
示例
输入 #1
2 ab cd
输出 #1
DRAW
输入 #2
2 xa ay
输出 #2
FIRST
输入 #3
3 aab bcb bac
输出 #3
DRAW
注意
考虑第一个样本:
好的字符串是字符串:a、ab、ac、abd、acd。
第一个玩家先移动并在字符串中添加字母 a,因为只有一个长度为 1 的好字符串。然后第二个玩家可以添加 b 或 c,游戏将以相应的字符串 abd 或 acd 结束。在第一种情况下,这将是平局(字符串有一个 a 和一个 b),在第二种情况下,第一个玩家获胜。当然,在这种情况下,第二个玩家更愿意选择字母 b 并以平局结束游戏。
考虑第二个示例:
好的字符串是:x、xa、xay。
我们可以看到游戏将以字符串 xay 结束,第一个玩家获胜。