D - Battle with E869120! Editorial /

Time Limit: 1 sec / Memory Limit: 256 MB



E869120 と対戦!
H \times W のマス目がある. 上から i 番目, 左から j 番目のマスを (i, j) と表す. E869120 君は, このマス目をつかう以下のゲームを考えた.
最初, マス (1, 1) に駒が置かれている. 各プレイヤーは交互に駒を 1 つずつ置いていくが, 駒を置けるマスは次の 2 つの条件を満たす必要がある.

  • このマスには駒が置かれていない.
  • 上下左右に隣り合ったマスのうち駒が置かれたマスが 1 つ以上ある.

先にマス (H, W) に駒を置いた方が勝ちである.
E869120 君はあなたにこのゲームで対戦を挑んできた. あなたは先手と後手の好きな方を選ぶことができる. あなたの目的はこのゲームに勝つことである.


この問題はインタラクティブ問題 (プログラムの入力と出力でジャッジとコミュニケーションをとる問題) であり, 入出力の形式が特殊である.

まず, マス目の行数と列数を表す 2 つの整数 HW が入力で与えられる.


続いて, あなたのプログラムは先手と後手のどちらを選ぶかを出力する. 先手の場合は First と, 後手の場合は Second と出力すればよい. 末尾には改行を入れること. これを出力するとゲームが開始する.
ゲームは, 先手の場合, (☆) からスタートし, 後手の場合 (★) からスタートする. ゲームが終了するまで (☆) と (★) を繰り返す.

(☆) 自分のターンである. あなたは駒を置くマス (x, y) を決め, 次のような形式で出力し, 末尾には改行を入れること.

x y

ただし, 出力形式を間違えたりルールに違反するような置き方をしたときの結果は不定である. また, 出力の最後に flush しなければならず, そうしない場合 TLE となることがある.

(★) E869120 君のターンである. あなたは次のような形式で E869120 君が置いたマス (X, Y) を受け取る.


ただし, (X, Y) = (-1, -1) のとき終わりを表し, あなたがマス (H, W) に駒を置いた直後に入力される. これはあなたが勝ったことを表し, その後直ちにプログラムを終了しなければならない.
また, (X, Y) = (H, W) のとき E869120 君の勝ちなので, この場合も直ちにプログラムを終了しなければならない.

すべてのケースにおいてあなたのプログラムが勝った場合正答とみなされる. さて, あなたは E869120 君に勝てるかな?


  • H1 以上 50 以下の整数.
  • W1 以上 50 以下の整数.
  • (H, W) \neq (1, 1).


小課題 1 [120 点]

  • H = 1.

小課題 2 [160 点]

  • 2 \leq H \leq 3.
  • 2 \leq W \leq 3.

小課題 3 [320 点]

  • 追加の制約はない.


入力 出力 コメント
1 2 H=1,W=2 であることが分かる.
First あなたは先手を選ぶ.
1 2 マス (1,2) に駒を置く.
-1 -1 あなたの勝ちである.

Max Score:600 points

Problem Statement

Battle with E869120!
There is a grid with H rows and W columns. The square at the i-th row and j-th column will be denoted as (i, j). E869120 came up with following game which uses this grid.
At first, there are a token at (1, 1). Each player is supposed to place a token in turns, but they can place token in the square if and only if this square satisfies both following two condutions:

  • There are no token in this square.
  • Among the 4-adjacent (up, down, left, right) square, there are at least one square which contains token.

The player who placed a token in (H, W) wins.
E869120 offered you to play this game. You can choose whether you play first or E869120 play first. Your objective is to win this game.

Input and Output

This problem is "interactive task" (the task which has to take communications with input and output of program), so the format of input/output is special.

At first, the number of rows H and the columns W, are given in the input in following format:


Then, your program must print whether you play first or E869120 plays first. If you play first, print First, otherwise, print Second. In the end you must put a line-break.

After that, the game starts. If you play first it will start from (☆), and if E869120 play first it will start from (★). It will repeat (☆) and (★) until the game ends.

(☆) It is your turn. Your program must decide where your program put a token. You must put line-break in the end.

x y

(★) It is E869120's turn. Your program will know the square (X, Y) which E869120 placed token from Standard Input in following format:


If (X, Y) = (-1, -1) it indicates the victory of your program, and it will be given after you put a token in (H, W). If (X, Y) = (H, W) it indicates that your program lost the game. In both case you have to terminate your program.

If your output format is invalid or the place that your program will put token is invalid, the verdict is undefined (it means it does not necessarily get WA). And also, you must flush Standard Output.**

Can you beat E869120?


  • H, W are integers between 1 and 50 (inclusive).
  • (H, W) \neq (1, 1).


Subtask 1 [120 points]

  • H = 1.

Subtask 2 [160 points]

  • 2 \leq H \leq 3.
  • 2 \leq W \leq 3.

Subtask 3 [320 points]

  • There are no additional constraints.

Sample Input / Output

Input Output Comment
1 2 You can know that H=1 and W=2.
First You chooses that you play first.
1 2 You put a token in square (1,2).
-1 -1 It means you won.