CF354B.Game with Strings

Given an n × n table T consisting of lowercase English letters. We'll consider some string s good if the table contains a correct path corresponding to the given string. In other words, good strings are all strings we can obtain by moving from the left upper cell of the table only to the right and down. Here's the formal definition of correct paths:

Consider rows of the table are numbered from 1 to n from top to bottom, and columns of the table are numbered from 1 to n from left to the right. Cell (r, c) is a cell of table T on the r-th row and in the c-th column. This cell corresponds to letter T__r, c.

A path of length k is a sequence of table cells [(_r_1, _c_1), (_r_2, _c_2), ..., (r__k, c__k)]. The following paths are correct:

1. There is only one correct path of length 1, that is, consisting of a single cell: [(1, 1)];
2. Let's assume that [(_r_1, _c_1), ..., (r__m, c__m)] is a correct path of length m, then paths [(_r_1, _c_1), ..., (r__m, c__m), (r__m + 1, c__m)] and [(_r_1, _c_1), ..., (r__m, c__m), (r__m, c__m + 1)] are correct paths of length m + 1.

We should assume that a path [(_r_1, _c_1), (_r_2, _c_2), ..., (r__k, c__k)] corresponds to a string of length k: _T__r_1, _c_1 + _T__r_2, _c_2 + ... + T__r__k, c__k.

Two players play the following game: initially they have an empty string. Then the players take turns to add a letter to the end of the string. After each move (adding a new letter) the resulting string must be good. The game ends after 2_n_ - 1 turns. A player wins by the following scenario:

1. If the resulting string has strictly more letters "a" than letters "b", then the first player wins;
2. If the resulting string has strictly more letters "b" than letters "a", then the second player wins;
3. If the resulting string has the same number of letters "a" and "b", then the players end the game with a draw.

Your task is to determine the result of the game provided that both players played optimally well.

给定一个由小写英文字母组成的 $n \times n$ 表格 $T$。若表格中存在一条对应于给定字符串的合法路径，则称该字符串 $s$ 为好字符串。换言之，“好字符串”即为所有可通过仅向右或向下移动、从表格左上角单元格出发所能得到的字符串。以下是合法路径的严格定义：

设表格的行从上到下编号为 $1$ 至 $n$，列从左到右编号为 $1$ 至 $n$。记 $(r, c)$ 为表格 $T$ 中第 $r$ 行、第 $c$ 列的单元格，其对应字母为 $T_{r,c}$。

长度为 $k$ 的路径是表格中的一组单元格序列：

$$(r_1, c_1),\ (r_2, c_2),\ \dots,\ (r_k, c_k).$$

以下路径称为合法路径：

1. 唯一的长度为 $1$ 的合法路径仅含单个单元格：$(1, 1)$；
2. 若 $(r_1, c_1),\ \dots,\ (r_m, c_m)$ 是长度为 $m$ 的合法路径，则以下两个长度为 $m+1$ 的路径也是合法的：

   $$(r_1, c_1),\ \dots,\ (r_m, c_m),\ (r_m + 1,\ c_m)$$

   和

   $$(r_1, c_1),\ \dots,\ (r_m, c_m),\ (r_m,\ c_m + 1).$$

我们定义路径 $(r_1, c_1),\ (r_2, c_2),\ \dots,\ (r_k, c_k)$ 对应一个长度为 $k$ 的字符串：

$$T_{r_1,c_1} + T_{r_2,c_2} + \dots + T_{r_k,c_k}.$$

两名玩家进行如下游戏：初始时字符串为空；随后双方轮流在字符串末尾添加一个字母。每次操作（即添加一个新字母）后，所得字符串必须为“好字符串”。游戏共进行 $2n - 1$ 轮后结束。胜负判定规则如下：

1. 若最终字符串中字母 'a' 的个数严格多于字母 'b' 的个数，则先手获胜；
2. 若最终字符串中字母 'b' 的个数严格多于字母 'a' 的个数，则后手获胜；
3. 若最终字符串中字母 'a' 与 'b' 的个数相等，则游戏以平局结束。

你的任务是：在双方均采取最优策略的前提下，判断该游戏的最终结果。

The first line contains a single number n (1 ≤ n ≤ 20).

Next n lines contain n lowercase English letters each — table T.

第一行包含一个整数 $n$（$1 \leq n \leq 20$）。

接下来的 $n$ 行，每行包含 $n$ 个小写英文字母 —— 表 $T$。

In a single line print string "FIRST", if the first player wins, "SECOND", if the second player wins and "DRAW", if the game ends with a draw.

在一行中输出字符串“FIRST”，如果先手玩家获胜；输出“SECOND”，如果后手玩家获胜；输出“DRAW”，如果游戏以平局结束。

Consider the first sample:

Good strings are strings: a, ab, ac, abd, acd.

The first player moves first and adds letter a to the string, as there is only one good string of length 1. Then the second player can add b or c and the game will end with strings abd or acd, correspondingly. In the first case it will be a draw (the string has one a and one b), in the second case the first player wins. Naturally, in this case the second player prefers to choose letter b and end the game with a draw.

Consider the second sample:

Good strings are: x, xa, xay.

We can see that the game will end with string xay and the first player wins.

考虑第一个样例：

好字符串为：a、ab、ac、abd、acd。

先手玩家首先行动，在字符串中添加字母 a，因为长度为 1 的好字符串仅有一个。随后，后手玩家可选择添加 b 或 c，游戏将分别以字符串 abd 或 acd 结束。在第一种情况下结果为平局（字符串中包含一个 a 和一个 b）；在第二种情况下先手玩家获胜。显然，此时后手玩家更倾向于选择字母 b，以平局结束游戏。

考虑第二个样例：

好字符串为：x、xa、xay。

可以看出，游戏将以字符串 xay 结束，且先手玩家获胜。