D - 1+1 解説 /

実行時間制限: 2 sec / メモリ制限: 64 MB

手を用いた遊びのひとつに 数字を増やす遊び というものがあります。
二人でやる遊びで、まず、両手の人差し指を出してお互いに見せ合います。
そして、交互に右手か左手のどちらかで相手の手のどちらかを選んで指の数を増やしていきます。
この問題は、このゲームを最善手でプレイしたときの勝敗を求める問題です。

入力

入力は以下の形式に従う。与えられる数は全て整数である。 
n m r
それぞれ以下のルールにおける 要素の状態数 n, 最大分割回数 m, 加算ルール r を表す。
  • 状態を (x,y) で表す。x, y を「要素」と呼ぶ。
  • 初期状態は、先攻後攻ともに (1,1) である。
  • 各ターンでとれる「行動」は「選択」または「分割」のいずれかである。
  • 先攻後攻交互に行動を繰り返し、(0,0) となったほうが負けとなる。
  • 選択： 自分の 0 でない要素 x と相手の 0 でない要素 y を選び、選んだ相手の要素に x を「加算」し、x+y にする。このとき、以下のどちらかの加算ルール r を適用する。
    • 加算ルール 0 ： x+y が n 以上になった場合は 0 になる。
    • 加算ルール 1 ： x+y が n 以上になった場合は x+y-n になる。
  • 分割： 一方の要素が 0、かつ、もう一方の要素 k が 2 以上ならば、「分割」を行うことができる。 a + b = k, a ≧ 1, b ≧ 1 となるような自然数 a, b を選び (a,b) とする。
    • 分割は最大 m 回行うことができる。

制約

  • 2 ≦ n ≦ 16
  • 0 ≦ m ≦ 2
  • 0 ≦ r ≦ 1

出力

無限に行動を続ける手順が存在するならば Infinite を出力せよ。 このとき、先手と後手は無限に行動を続けるために協力して良い。
存在しないならば、先手と後手は以下の基準で行動を選んだとき、 ゲームの結果とゲームが何ターンで終了するかを求めよ。 そして、先手が勝つ場合は First、後手が勝つ場合は Second と 1 行目に出力せよ。 2 行目にゲームが終了するのが何ターン目になるのかを出力せよ。
  1. 自分が勝ちになる手が存在するときはその手を選ぶ。自分が勝ちになる手が複数存在するときはその中からゲームが最短で終了するような手を選ぶ。
  2. 自分が負けになる手しか存在しないとき、ゲームが最長で終了するような手を選ぶ。

Input 1

2 0 0

Output 1

First
3

Input 2

4 0 1

Output 2

Infinite