OUPC2024 Day2 : 北海道大学セット
コンテスト日時
2025/03/16 (Su) 12:00 - 16:00

G - Divisor Game

Milk
2
s
1024
MB
100

問題文

itigo くんと Today くんは Divisor Game というゲームで遊んでいます。
Divisor Game のルールは次のとおりです。

  • 開始時には $N$ 個の石がある
  • $2$ 人のプレイヤーが itigo くんから順に、交互に次の操作を行う
    • 残りの石の個数を $x$ とする。$x$ の正の約数のうち好きな数を選び、その数だけ石を捨てる
  • 操作を行った結果、残りの石の個数が $1$ 個以下になったとき、その操作を行ったプレイヤーが負けで、負けでない方が勝ちとなる

互いに最適に行動したとき、先手の itigo くんと後手の Today くんのどちらが勝つか判定してください。
なお、このゲームは必ず有限回の操作で勝敗がつくことが証明できます。

制約

  • $2 \leq N \leq 10^{9}$
  • 入力はすべて整数である

入力

入力は以下の形式で標準入力から与えられます。

$N$

出力

先手の itigo くんが勝つ場合は First、後手の Today くんが勝つ場合は Second と出力してください。

入力例 1
3
出力例 1
First

例えば、ゲームは以下のように進行します。

  • 先手の itigo くんが $3$ の約数から $1$ を選択する。石の個数は $2$ となる。
  • $2$ の約数は $1$ と $2$ であり、どちらを選択しても石の個数は $1$ 以下となる。したがって後手の Today くんは負けとなり、先手の itigo くんが勝ちとなる。

実際には、このケースでは先手の itigo くんが最適な行動を取れば常に itigo くんが勝者となることを示せます。
したがって、First と出力してください。

入力例 2
378292877
出力例 2
Second
提出
C++23 (g++ 12.2.0)