Codeforces Round 206 (Div. 1) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

bitmasks

dp

games

*2400

No tag edit access

The problem statement has recently been changed. View the changes.

×
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-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/13/2024 16:51:16 (i2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|