Problem3759--Help Shrek and Donkey 2

3759: Help Shrek and Donkey 2

Time Limit: 2 Sec  Memory Limit: 256 MB
Submit: 0  Solved: 0
[Submit] [Status] [Web Board] [Creator:]

Description

time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Having learned (not without some help from the Codeforces participants) to play the card game from the previous round optimally, Shrek and Donkey (as you may remember, they too live now in the Kingdom of Far Far Away) have decided to quit the boring card games and play with toy soldiers.

The rules of the game are as follows: there is a battlefield, its size equals n×m squares, some squares contain the toy soldiers (the green ones belong to Shrek and the red ones belong to Donkey). Besides, each of the n lines of the area contains not more than two soldiers. During a move a players should select not less than 1 and not more than k soldiers belonging to him and make them either attack or retreat.

An attack is moving all of the selected soldiers along the lines on which they stand in the direction of an enemy soldier, if he is in this line. If this line doesn't have an enemy soldier, then the selected soldier on this line can move in any direction during the player's move. Each selected soldier has to move at least by one cell. Different soldiers can move by a different number of cells. During the attack the soldiers are not allowed to cross the cells where other soldiers stand (or stood immediately before the attack). It is also not allowed to go beyond the battlefield or finish the attack in the cells, where other soldiers stand (or stood immediately before attack).

A retreat is moving all of the selected soldiers along the lines on which they stand in the direction from an enemy soldier, if he is in this line. The other rules repeat the rules of the attack.

For example, let's suppose that the original battlefield had the form (here symbols "G" mark Shrek's green soldiers and symbols "R" mark Donkey's red ones):

-G-R-
-R-G-

Let's suppose that k=2 and Shrek moves first. If he decides to attack, then after his move the battlefield can look like that:

--GR-     --GR-     -G-R-
-RG-- -R-G- -RG--

If in the previous example Shrek decides to retreat, then after his move the battlefield can look like that:

G--R-     G--R-     -G-R-
-R--G -R-G- -R--G

On the other hand, the followings fields cannot result from Shrek's correct move:

G--R-     ---RG     --GR-
-RG-- -R-G- GR---

Shrek starts the game. To make a move means to attack or to retreat by the rules. A player who cannot make a move loses and his opponent is the winner. Determine the winner of the given toy soldier game if Shrek and Donkey continue to be under the yellow pills from the last rounds' problem. Thus, they always play optimally (that is, they try to win if it is possible, or finish the game in a draw, by ensuring that it lasts forever, if they cannot win).

Input

The first line contains space-separated integers n, m and k (1≤n,m,k≤100). Then n lines contain m characters each. These characters belong to the set {"-", "G", "R"}, denoting, respectively, a battlefield's free cell, a cell occupied by Shrek's soldiers and a cell occupied by Donkey's soldiers.

It is guaranteed that each line contains no more than two soldiers.

Output

Print "First" (without the quotes) if Shrek wins in the given Toy Soldier game. If Donkey wins, print "Second" (without the quotes). If the game continues forever, print "Draw" (also without the quotes).

Examples
Input
2 3 1
R-G
RG-
Output
First
Input
3 3 2
G-R
R-G
G-R
Output
Second
Input
2 3 1
-R-
-G-
Output
Draw
Input
2 5 2
-G-R-
-R-G-
Output
First

Source/Category