Problem 29: Nim Game Variation

Problem Statement: Given n piles of stones, where the i-th pile has a[i] stones, determine the winner of the nim game assuming both players play optimally. Print "First" if the first player wins and "Second" otherwise.

Input

The first line contains an integer n. The second line contains n space-separated integers representing the piles.

Output

Print "First" if the first player wins, otherwise print "Second".

Examples


Input:
3
1 2 3

Output:
Second

Solution Explanation

Method 1: Compute the nim-sum (bitwise XOR) of all pile sizes; if it is nonzero, the first player wins; if it is zero, the second player wins. Method 2: Simulate the game recursively; however, the nim-sum method is more efficient for optimal play.

Solution in C++


#include 
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; cin >> n;
    int xorSum = 0;
    for(int i = 0; i < n; i++){
        int x; cin >> x;
        xorSum ^= x;
    }
    cout << (xorSum ? "First" : "Second") << "
";
    return 0;
}