Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

No tag edit access

B. Game with Strings

time limit per test

1 secondmemory limit per test

512 megabytesinput

standard inputoutput

standard outputGiven 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:

- There is only one correct path of length 1, that is, consisting of a single cell: [(1, 1)];
- 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*_{r1, c1} + *T*_{r2, c2} + ... + *T*_{rk, 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 2*n* - 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.

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.

Examples

Input

2

ab

cd

Output

DRAW

Input

2

xa

ay

Output

FIRST

Input

3

aab

bcb

bac

Output

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.

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/13/2018 12:54:10 (d3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|