Game with Strings
Description
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 Tr, c.
A path of length k is a sequence of table cells [(r1, c1), (r2, c2), ..., (rk, ck)]. The following paths are correct:
- There is only one correct path of length 1, that is, consisting of a single cell: [(1, 1)];
- Let's assume that [(r1, c1), ..., (rm, cm)] is a correct path of length m, then paths [(r1, c1), ..., (rm, cm), (rm + 1, cm)] and [(r1, c1), ..., (rm, cm), (rm, cm + 1)] are correct paths of length m + 1.
We should assume that a path [(r1, c1), (r2, c2), ..., (rk, ck)] corresponds to a string of length k: Tr1, c1 + Tr2, c2 + ... + Trk, ck.
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 2n - 1 turns. A player wins by the following scenario:
- If the resulting string has strictly more letters "a" than letters "b", then the first player wins;
- If the resulting string has strictly more letters "b" than letters "a", then the second player wins;
- 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.
The first line contains a single number n (1 ≤ n ≤ 20).
Next n lines contain n lowercase English letters each — table 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.
Input
The first line contains a single number n (1 ≤ n ≤ 20).
Next n lines contain n lowercase English letters each — table T.
Output
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.
Samples
2
ab
cd
DRAW
2
xa
ay
FIRST
3
aab
bcb
bac
DRAW
Note
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.