C - Piles of Pebbles Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

小石の山が N 個あります．最初，i 番目の山には A_i 個の小石があります．

これらを用いて，高橋君と青木君がゲームをします． 高橋君から始めて，交互に次の操作を行い，操作を行えなくなった方が負けとなります．

  • 山を 1 つ以上選び，選んだそれぞれの山から，高橋君の操作の場合は X 個ずつ，青木君の操作の場合は Y 個ずつ小石を取り除く． ただし，小石の個数が足りない山を選ぶことはできない．

二人が最適に行動したとき，どちらがゲームに勝つかを求めてください.

制約

  • 1 \leq N \leq 2\times 10^5
  • 1 \leq X, Y \leq 10^9
  • 1 \leq A_i \leq 10^9

入力

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

N X Y
A_1 A_2 \cdots A_N

出力

このゲームに勝つのが高橋君の場合 First を，青木君の場合 Second を出力せよ．

入力例 1

2 1 1
3 3

出力例 1

First

例えば，以下のようなゲームの進行が考えられます．

  • 高橋君が両方の山から石を 1 つ取り除く．
  • 青木君が 1 番目の山から石を 1 つ取り除く．
  • 高橋君が 1 番目の山から石を 1 つ取り除く．
  • 青木君が 2 番目の山から石を 1 つ取り除く．
  • 高橋君が 2 番目の山から石を 1 つ取り除く．

青木君がどのように操作を行っても高橋君が勝つことができるので，答えは First です．

入力例 2

2 1 2
3 3

出力例 2

Second

Score : 600 points

Problem Statement

There are N piles of pebbles. Initially, the i-th pile has A_i pebbles.

Takahashi and Aoki will play a game using these piles. They will alternately perform the following operation, with Takahashi going first, and the one who becomes unable to do so loses the game.

  • Choose one or more piles, and remove the following number of pebbles from each chosen pile: X pebbles if this operation is performed by Takahashi, and Y pebbles if performed by Aoki. Here, a pile with an insufficient number of pebbles cannot be chosen.

Determine the winner of the game if both players play optimally.

Constraints

  • 1 \leq N \leq 2\times 10^5
  • 1 \leq X, Y \leq 10^9
  • 1 \leq A_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N X Y
A_1 A_2 \cdots A_N

Output

If it is Takahashi who will win the game, print First; if it is Aoki, print Second.

Sample Input 1

2 1 1
3 3

Sample Output 1

First

Here is one possible progression of the game.

  • Takahashi removes 1 pebble from both piles.
  • Aoki removes 1 pebble from the 1-st pile.
  • Takahashi removes 1 pebble from the 1-st pile.
  • Aoki removes 1 pebble from the 2-nd pile.
  • Takahashi removes 1 pebble from the 2-nd pile.

No matter how Aoki plays, Takahashi can always win, so the answer is First.

Sample Input 2

2 1 2
3 3

Sample Output 2

Second