Codeforces Round 102 (Div. 1)
D
Help Shrek and Donkey 2
Codeforces
2600
原题
← CE →
翻译中…

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).

翻译中…

样例

Input #1
2 3 1
R-G
RG-
Output #1
First
InputCopy OutputCopy
Input #2
3 3 2
G-R
R-G
G-R
Output #2
Second
InputCopy OutputCopy
Input #3
2 3 1
-R-
-G-
Output #3
Draw
InputCopy OutputCopy
Input #4
2 5 2
-G-R-
-R-G-
Output #4
First
InputCopy OutputCopy
题目信息
题号
142D
时间限制
2 s
内存限制
256 MB
标签
博弈论

题面与样例版权归 Codeforces 及出题人所有;中文翻译由 AI 生成(CI 管线),如有出入请以原文为准。