/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 800 点
問題文
先手太郎君と後手次郎君はお母さんへのプレゼントに長方形のケーキを買ってきました。 先手太郎君と後手次郎君はおなかが空いたので、お母さん用の 1 ピースを残して全て食べてしまうことにしました。
N 行 M 列に並ぶピースからなるケーキがあります。
上から i 行目、左から j 列目のピースには、s_{i,j} が 1 のときイチゴが載っており、0 のときイチゴが載っていません。
先手太郎君からはじめて、二人は残りのピースが 1 個になるまで交互にケーキに操作を行います。 二人が行うことができる操作は以下の通りです。ただし、残りの全てのピースを食べてしまうような操作を行うことはできません。
- 上から 1 行目に並ぶピースを全て食べる
- 下から 1 行目に並ぶピースを全て食べる
- 左から 1 列目に並ぶピースを全て食べる
- 右から 1 列目に並ぶピースを全て食べる
先手太郎君はイチゴが載っているピースを、後手次郎君はイチゴが載っていないピースを残したいです。 先手太郎君が適切に操作を行ったとき、後手次郎君がどのように操作を行ったとしてもイチゴが載っているピースを残すことができるかどうかを判定してください。
T 個のテストケースが与えられるので、それぞれについて答えを求めてください。
制約
- 1 \le T \le 10^5
- 1 \le N,M \le 10^{3}
- 1<NM
- s_{i} は
0と1のみからなる長さ M の文字列 - 全てのテストケースにおける NM の総和は 10^6 以下
入力
入力は以下の形式で標準入力から与えられる。
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
各テストケースは以下の形式で与えられる。
N M s_1 s_2 \vdots s_N
出力
T 行出力せよ。
i 行目には i 番目のテストケースについて、先手太郎君が適切に操作を行ったとき、後手次郎君がどのように操作を行ったとしてもイチゴが載っているピースを残すことができるなら First を、そうでなければ Second を出力せよ。
入力例 1
4 2 2 01 10 1 4 0100 4 1 0 1 0 0 5 5 00000 11100 01011 00100 01101
出力例 1
Second First First Second
1 番目のテストケースについて、先手太郎君がどのような操作を行っても後手二郎君はイチゴの載っていないピースを残すことができます。
2 番目のテストケースについて、先手太郎君が適切に操作を行うことで後手次郎君がどのように操作を行ったとしてもイチゴが載っているピースを残すことができます。
残りの全てのピースを食べてしまうような操作は選べないことに注意してください。
Score : 800 points
Problem Statement
Taro the First and Jiro the Second bought a rectangular cake as a present for their mother. They were hungry, so they decided to eat all of the cake except for one piece for their mother.
There is a cake consisting of pieces arranged in N rows and M columns.
The piece at the i-th row from the top and j-th column from the left has a strawberry on it when s_{i,j} is 1, and does not have a strawberry when it is 0.
Starting with Taro the First, the two alternately perform an operation on the cake until only one piece remains. The operations they can perform are as follows. However, they cannot perform an operation that eats all remaining pieces.
- Eat all pieces in the first row from the top
- Eat all pieces in the first row from the bottom
- Eat all pieces in the first column from the left
- Eat all pieces in the first column from the right
Taro the First wants to leave a piece with a strawberry, and Jiro the Second wants to leave a piece without a strawberry. Determine whether Taro the First can leave a piece with a strawberry no matter how Jiro the Second operates, when Taro operates appropriately.
You are given T test cases; find the answer for each of them.
Constraints
- 1 \le T \le 10^5
- 1 \le N,M \le 10^{3}
- 1<NM
- s_{i} is a string of length M consisting of
0and1. - The sum of NM over all test cases is at most 10^6.
Input
The input is given from Standard Input in the following format:
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
Each test case is given in the following format:
N M s_1 s_2 \vdots s_N
Output
Print T lines.
On the i-th line, for the i-th test case, print First if Taro the First can leave a piece with a strawberry no matter how Jiro the Second operates when Taro operates appropriately, and Second otherwise.
Sample Input 1
4 2 2 01 10 1 4 0100 4 1 0 1 0 0 5 5 00000 11100 01011 00100 01101
Sample Output 1
Second First First Second
For the first test case, no matter what operation Taro performs, Jiro can leave a piece without a strawberry.
For the second test case, if Taro operates appropriately, he can leave a piece with a strawberry no matter how Jiro operates.
Note that they cannot choose an operation that eats all remaining pieces.