D - Decrementing Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 1000 点

問題文

黒板に N 個の整数が書かれています。i 番目の整数は A_i であり、これらの最大公約数は 1 です。

高橋君と青木君はこの数を使ってゲームをします。ゲームでは高橋君から始めて交互に以下の操作を繰り返します。

  • 黒板の中から 2 以上の数を 1 つ選び、その数から 1 を引く。
  • その後、黒板に書かれた数の最大公約数を g として、すべての数を g で割る。

黒板に書かれた数が全て 1 となっていて、操作が行えない人の負けです。 二人が最適に行動したとき、どちらが勝つか求めてください。

制約

  • 1 ≦ N ≦ 10^5
  • 1 ≦ A_i ≦ 10^9
  • A_1 から A_N の最大公約数は 1

入力

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

N
A_1 A_2 … A_N

出力

先手の高橋君が勝つなら First を、後手の青木君が勝つなら Second を出力せよ。

入力例 1

3
3 6 7

出力例 1

First

以下のようにすれば先手の高橋君が勝てます。

  • 高橋君が 7 から 1 を引く。このとき、操作後は (1,2,2) となる。
  • 青木君が 2 から 1 を引く。このとき、操作後は (1,1,2) となる。
  • 高橋君が 2 から 1 を引く。このとき、操作後は (1,1,1) となる。

入力例 2

4
1 2 4 8

出力例 2

First

入力例 3

5
7 8 8 8 8

出力例 3

Second

Score : 1000 points

Problem Statement

There are N integers written on a blackboard. The i-th integer is A_i, and the greatest common divisor of these integers is 1.

Takahashi and Aoki will play a game using these integers. In this game, starting from Takahashi the two player alternately perform the following operation:

  • Select one integer on the blackboard that is not less than 2, and subtract 1 from the integer.
  • Then, divide all the integers on the black board by g, where g is the greatest common divisor of the integers written on the blackboard.

The player who is left with only 1s on the blackboard and thus cannot perform the operation, loses the game. Assuming that both players play optimally, determine the winner of the game.

Constraints

  • 1 ≦ N ≦ 10^5
  • 1 ≦ A_i ≦ 10^9
  • The greatest common divisor of the integers from A_1 through A_N is 1.

Input

The input is given from Standard Input in the following format:

N
A_1 A_2 … A_N

Output

If Takahashi will win, print First. If Aoki will win, print Second.

Sample Input 1

3
3 6 7

Sample Output 1

First

Takahashi, the first player, can win as follows:

  • Takahashi subtracts 1 from 7. Then, the integers become: (1,2,2).
  • Aoki subtracts 1 from 2. Then, the integers become: (1,1,2).
  • Takahashi subtracts 1 from 2. Then, the integers become: (1,1,1).

Sample Input 2

4
1 2 4 8

Sample Output 2

First

Sample Input 3

5
7 8 8 8 8

Sample Output 3

Second