B. Игра со строками
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Задана таблица T размера n × n, состоящая из строчных латинских букв. Строка s считается хорошей, если в таблице существует корректный путь, соответствующий данной строке. Другими словами, хорошими считаются все строки, которые можно получить, двигаясь из левой верхней клетки таблицы только вправо и вниз. Далее — формальное определение этого понятия:

Пронумеруем строки таблицы сверху вниз от 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», если игра закончится в ничью.

Примеры
Входные данные
2
ab
cd
Выходные данные
DRAW
Входные данные
2
xa
ay
Выходные данные
FIRST
Входные данные
3
aab
bcb
bac
Выходные данные
DRAW
Примечание

Рассмотрим первый пример:

Хорошими строками являются: a, ab, ac, abd, acd.

Первый игрок в первый ход допишет к строке букву a, так как существует всего одна хорошая строка длины 1. Затем, второй игрок может приписать одну из букв b или c и тогда игра закончится соответственно со строками abd или acd. В первом случае будет ничья (в строке по одной букве a и b), во втором же случае выиграет первый игрок. Понятно, что в таком случае второму игроку выгодно выбрать букву b и получить ничью.

Рассмотрим второй пример:

Хорошие строки: x, xa, xay.

Понятно, что игра закончится со строкой xay и победит первый игрок.