N - Matrix Game
Editorial
/
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
2 \times 2 行列 A = \begin{pmatrix} a & b \\ c & d \end{pmatrix} が与えられます。A の要素は非負整数です。
あおばさんとひろせさんがこの行列を用いてゲームをします。あおばさんが先手で、交互に以下の行動をします。
- A の行または列を一つ選んで、選んだ行または列の各要素から同じ正整数を引く。このとき、A の要素が負になってはいけない。
行動ができなくなった方の負けで、負けなかった方が勝ちです。両者がそれぞれ自身が勝つために最適な戦略をとる場合に、どちらが勝つかを判定してください。
T 個のテストケースが与えられるので、それぞれについて答えを求めてください。
制約
- 1 \leq T \leq 1000
- 0 \leq a, b, c, d \leq 10^9
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
T a_1 b_1 c_1 d_1 a_2 b_2 c_2 d_2 \vdots a_T b_T c_T d_T
出力
各テストケースに対し、あおばさんが勝利するなら First
を、ひろせさんが勝利するなら Second
を出力せよ。
入力例 1
4 1 3 5 0 3 0 0 7 3 1 4 1 5 9 2 5
出力例 1
First Second First Second
1 ケース目で与えられる行列は \begin{pmatrix} 1 & 3 \\ 5 & 0 \end{pmatrix} です。先手が 1 行目から 1 を引くことで行列は \begin{pmatrix} 0 & 2 \\ 5 & 0 \end{pmatrix} となり、後手は操作が行えないので先手の勝ちです。