CF142D.Help Shrek and Donkey 2

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

在上一轮比赛中（在 Codeforces 参赛者的帮助下）学会了如何最优地玩卡牌游戏后，史瑞克（Shrek）和驴子（Donkey）（如你所知，他们如今也居住在“远得不能再远王国”）决定放弃枯燥的卡牌游戏，转而改玩玩具士兵。

游戏规则如下：战场上共有 $n \times m$ 个方格，其中一些方格放置有玩具士兵（绿色士兵属于史瑞克，红色士兵属于驴子）。此外，战场的每一行至多包含两名士兵。在一次行动中，玩家需选择自己所属的至少 $1$ 名、至多 $k$ 名士兵，并令其全部执行“进攻”或“撤退”。

进攻：将所有被选中的士兵沿其所在行朝向敌方士兵的方向移动（若该行中存在敌方士兵）；若该行中没有敌方士兵，则该行上被选中的士兵可在玩家本轮行动中朝任意方向移动。每名被选中的士兵必须至少移动一格；不同士兵可移动不同格数。进攻过程中，士兵不得穿越其他士兵所在格（或这些士兵在进攻开始前瞬间所占据的格子）；也不得移出战场边界，或最终停驻于其他士兵所在格（或这些士兵在进攻开始前瞬间所占据的格子）。

撤退：将所有被选中的士兵沿其所在行朝远离敌方士兵的方向移动（若该行中存在敌方士兵）；其余规则与进攻完全相同。

例如，假设初始战场如下（其中符号 “G” 表示史瑞克的绿色士兵，“R” 表示驴子的红色士兵）：

-G-R-  
-R-G-  

设 $k = 2$，且由史瑞克先行。若他选择进攻，则其行动后战场可能变为以下任意一种情形：

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

若在上述例子中史瑞克选择撤退，则其行动后战场可能变为以下任意一种情形：

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

另一方面，以下局面不可能通过史瑞克的一次合法行动得到：

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

史瑞克首先行动。一次行动即依上述规则执行一次进攻或撤退。无法行动的玩家判负，其对手获胜。请判断：在给定的玩具士兵游戏中，若史瑞克与驴子仍受上一轮题目中“黄色药丸”的影响（即始终以最优策略进行游戏——若能获胜则必胜；若无法获胜，则力求使游戏永远持续下去以达成平局），谁将获胜？

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.

第一行包含三个用空格分隔的整数 $n$、$m$ 和 $k$（$1 \leq n, m, k \leq 100$）。接下来的 $n$ 行，每行包含 $m$ 个字符。这些字符属于集合 \{"\-","G","R"\}，分别表示战场上的空闲格子、史莱克士兵占据的格子以及驴子士兵占据的格子。

保证每一行中至多包含两名士兵。

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

如果史莱克在给定的玩具士兵游戏中获胜，则输出 "First"（不带引号）；如果驴子获胜，则输出 "Second"（不带引号）；如果游戏永远进行下去，则输出 "Draw"（同样不带引号）。