题目描述

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

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

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

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

输入格式

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

$N$ $A_1$ $A_2$ … $A_N$

输出格式

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

题目大意

题目描述

黑板上写着 $N$ 个整数。第 $i$ 个整数是 $A_i$ ，它们的最大公约数为 $1$ 。

高桥君和青木君将使用这些数来玩一个游戏。高桥君在这个游戏中是先手，他们将轮流进行以下操作（以下两步相当于一次操作）：

• 选择黑板中大于 $1$ 的一个数，将其减 $1$ 。
• 此后，将黑板上所有数全部除以所有数的最大公约数。

当黑板上的数全部为 $1$ 时，不能再进行操作的人就失败了。两人都选择最好的方式行动，请求出哪边会最终胜利。

数据范围

• $1 \leq N \leq 10^5$
• $1 \leq A_i \leq 10^9$
• 从 $A_1$ 到 $A_N$ 的所有数的最大公约数为 $1$ 。

输入

输入按以下格式：

$$N$$ $$A_1 A_2 \dots A_N$$

输出

如果先手的高桥君获胜了，则输出First。如果后手的青木君获胜了，则输出Second。

样例1解释

按以下情况高桥君将胜利：

• 高桥君将 $7$ 减去 $1$ 。操作后黑板上的数为 $(1,2,2)$ 。
• 青木君将 $2$ 减去 $1$ 。操作后黑板上的数为 $(1,1,2)$ 。
• 高桥君将 $2$ 减去 $1$ 。操作后黑板上的数为 $(1,1,1)$ 。

3
3 6 7

First

4
1 2 4 8

First

5
7 8 8 8 8

Second

提示

制約

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

Sample Explanation 1

以下のようにすれば先手の高橋君が勝てます。 - 高橋君が $7$ から $1$ を引く。このとき、操作後は $(1,2,2)$ となる。 - 青木君が $2$ から $1$ を引く。このとき、操作後は $(1,1,2)$ となる。 - 高橋君が $2$ から $1$ を引く。このとき、操作後は $(1,1,1)$ となる。