分数: 800 点
问题陈述
一太郎和二郎二郎买了一个长方形的蛋糕作为送给母亲的礼物。 他们饿了,所以他们决定把蛋糕全部吃掉,只留下一块给妈妈。
有一个蛋糕,由排列成不同形状的碎片组成。 N 行和 M 列。
这件作品位于 i从顶部开始的第行和 j左边第 1 列有一个草莓,当 s_{i,j} is 1,并且没有草莓 0.
从一号太郎开始,两人交替对蛋糕进行操作,直到只剩下一块。 他们可以执行的操作如下。然而,它们无法执行吃掉所有剩余碎片的操作。
- 吃掉从上往下第一行的所有棋子
- 吃掉第一行从底部开始的所有棋子
- 吃掉左边第一列的所有棋子
- 吃掉右边第一列中的所有棋子
第一太郎想要留下一块有草莓的东西,第二郎想要留下一块没有草莓的东西。 确定当太郎操作得当时,无论二郎如何操作,一太郎是否都能留下一块草莓。
你被给予 T 测试用例;为他们每个人找到答案。
约束
- 1 \le T \le 10^5
- 1 \le N,M \le 10^{3}
- 1<NM
- s_{i} 是一个长度为 M 组成
0和1. - 总和 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
对于第一个测试用例,无论太郎执行什么操作,二郎都可以留下一块没有草莓的东西。
对于第二个测试用例,如果太郎操作得当,无论二郎如何操作,他都可以留下一块草莓。
请注意,他们无法选择吃掉所有剩余棋子的操作。