Help Shrek and Donkey 2

题意翻译

- 给定一个 $n\times m$ 的棋盘。棋盘中 `-` 代表空格，`G` 代表绿色棋子，`R` 代表红色棋子。每行至多有两个士兵。 - 先手执绿棋。 - 每个回合玩家可以选择 $1$ 到 $k$ 个棋子在当前行内向左或向右任意移动一次，但不能越过另一个棋子，也不能在不同行之间移动。 - 若一方在移动后能使另一方无法移动，则获胜。 - 求最后谁获胜或平局。 - $1\leq n,m,k\leq 100$。

题目描述

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-<br></br>-R-G-<br></br>` 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-<br></br>-RG-- -R-G- -RG--<br></br>` 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-<br></br>-R--G -R-G- -R--G<br></br>` On the other hand, the followings fields cannot result from Shrek's correct move: `G--R- ---RG --GR-<br></br>-RG-- -R-G- GR---<br></br>` 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).

输入输出格式

输入格式

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.

输出格式

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

输入输出样例

输入样例 #1

2 3 1
R-G
RG-

输出样例 #1

First

输入样例 #2

3 3 2
G-R
R-G
G-R

输出样例 #2

Second

输入样例 #3

2 3 1
-R-
-G-

输出样例 #3

Draw

输入样例 #4

2 5 2
-G-R-
-R-G-

输出样例 #4

First