C - Snukeと対戦!

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

Cat Snukeは囲碁をたまに打つ。Snukeは碁石を使った以下のような新たなゲームを思いついた。

  • HW 列のマス目を書く。
  • 2 人で交互に マスの中 に碁石を 1 つずつ置いていく。碁石の色には黒と白の 2 種類があるが、このうちどちらの色の石を置いても良い。
  • すでに碁石が置かれているマスには碁石を置くことはできない。また、上下左右に直接隣り合うマスに、置こうとしている石と同じ色の石が 1 つでも 置かれている場合も置くことができない。
  • 碁石を置くことができなくなったプレイヤーが負けとなり、もう一方のプレイヤーが勝ちとなる。

Snukeはあなたにこのゲームで対戦を挑んできた。あなたは先手と後手の好きな方を選ぶことができる。あなたの目的はこのゲームに勝つことである。


入出力

まず、マス目の行数と列数をあらわす 2 つの整数 H (1 ≦ H ≦ 18), W (1 ≦ W ≦ 18) が空白区切りで標準入力に与えられる。

H W

続いて、あなたのプログラムは先手と後手のどちらを選ぶかを出力する。先手の場合は First を、後手の場合は Second を出力すれば良い。末尾には改行を入れること。

先手か後手かを出力すると直ちにゲームが開始される。

先手を選んだ場合は、以下のような流れでゲームを進める。

(★)まず、あなたは碁石を置く場所と置く碁石の色の情報を表す 3 つの整数 a (1 ≦ a ≦ H), b (1 ≦ b ≦ W), c (0 ≦ c ≦ 1) を空白区切りで出力する。これは、あなたが a 行目 b 列目に 色 c の碁石を置くということを表すことになる。ただし、色 0 は黒、色 1 は白を表すものとする。末尾には改行を入れること。

a b c

このとき、 ルールに違反するような置き方をしようとした場合には直ちに不正解となる。この場合のジャッジ結果は不定である(必ずしも WA になるとは限らない)。 また、正しくないフォーマットで出力をした場合の結果も不定である。

(△)次に、Snukeが碁石を置く場所と置く碁石の色の情報を表す 3 つの整数 A (1 ≦ A ≦ H), B (1 ≦ B ≦ W), C (0 ≦ C ≦ 1) が空白区切りで与えられる。これは、Snukeが A 行目 B 列目に 色 C の碁石を置くということを表す。ただし、A = B = C = -1 の場合はSnukeが碁石を置く場所がなくなりあなたがゲームに勝ったことを表す。この場合、 あなたのプログラムは直ちに終了しなければならない。 終了しなかった場合のジャッジ結果は不定である。

A B C

ゲームが終了するまで、(★)と(△)を交互に繰り返す。

あなたのプログラムがゲームに勝って終了した場合、正答とみなされる。

また、後手を選んだ場合は、(★)のステップを飛ばして(△)のステップから処理を行う。

出力した後に、出力をflushしなければならないことに注意せよ。flushしなかった場合、TLEとなることがある。

各言語での入出力の方法は過去の AtCoder で出題されている問題 (リンク: ABC 019 D: 高橋くんと木の直径) を参考にしてもよい。

入出力例

説明 プログラムの出力 プログラムへの入力
マス目の行数と列数が与えられている。 2 2
後手を選ぶということを答えている。 Second
Snukeが碁石を置く場所と、置く碁石の色の情報が与えられている。 1 2 0
あなたが碁石を置く場所と、置く碁石の色の情報を答えている。 2 2 1
Snukeが碁石を置く場所と、置く碁石の色の情報が与えられている。 1 1 1
あなたが碁石を置く場所と、置く碁石の色の情報を答えている。 2 1 0
Snukeが碁石を置くことができなくなったという情報が与えられている。 -1 -1 -1