p328.ans1
======================
SECOND

=================
p328.ans2
======================
FIRST

=================
p328.cpp
======================
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int n;
string s;

void read() { cin >> n >> s; }

int sg_match(int len) { return len >= 1 ? 1 : 0; }
int sg_diff(int len) { return 0; }
int sg_boundary(int len) { return len; }
int sg_free(int len) { return len % 2; }

void solve() {
    // This is a combinatorial game theory problem. We can use Sprague-Grundy
    // theorem: the game splits into independent segments of uncolored vertices,
    // and the overall SG value is the XOR of individual segment SG values.
    //
    // Each segment has boundary conditions based on neighboring colored
    // vertices:
    // - "match": both neighbors have the same color (e.g., 1...1 or 2...2).
    // - "diff": neighbors have different colors (e.g., 1...2 or 2...1).
    // - "boundary": one neighbor colored, other side is chain end (free)
    // - "free": both sides are chain ends (no colored neighbors)
    //
    // Computing SG values naively via mex is O(N^2), but we can spot the
    // pattern, as it's fairly similar:
    //
    // len | match | diff | boundary | free
    // ----|-------|------|----------|-----
    //   0 |     0 |    0 |        0 |    0
    //   1 |     1 |    0 |        1 |    1
    //   2 |     1 |    0 |        2 |    0
    //   3 |     1 |    0 |        3 |    1
    //   4 |     1 |    0 |        4 |    0
    //   5 |     1 |    0 |        5 |    1
    //   6 |     1 |    0 |        6 |    0
    //   7 |     1 |    0 |        7 |    1
    //   8 |     1 |    0 |        8 |    0
    //   9 |     1 |    0 |        9 |    1
    //  10 |     1 |    0 |       10 |    0
    //
    // So: sg_match(len)    = (len >= 1) ? 1 : 0
    //     sg_diff(len)     = 0
    //     sg_boundary(len) = len
    //     sg_free(len)     = len % 2

    int xor_sum = 0;
    int i = 0;

    while(i < n) {
        if(s[i] == '0') {
            int start = i;
            while(i < n && s[i] == '0') {
                i++;
            }
            int len = i - start;

            char left = (start > 0) ? s[start - 1] : 0;
            char right = (i < n) ? s[i] : 0;

            int sg;
            if(left == 0 && right == 0) {
                sg = sg_free(len);
            } else if(left == 0 || right == 0) {
                sg = sg_boundary(len);
            } else if(left == right) {
                sg = sg_match(len);
            } else {
                sg = sg_diff(len);
            }
            xor_sum ^= sg;
        } else {
            i++;
        }
    }

    cout << (xor_sum != 0 ? "FIRST" : "SECOND") << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}

=================
p328.in1
======================
5
00100

=================
p328.in2
======================
4
1020

=================
statement.txt
======================
328. A Coloring Game
Time limit per test: 0.25 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



Two players play a graph coloring game. They make moves in turn, first player moves first. Initially they take some undirected graph. At each move, a player can color an uncolored vertex with either white or black color (each player can use any color, possibly different at different turns). It's not allowed to color two adjacent vertices with the same color. A player that can't move loses.

After playing this game for some time, they decided to study it. For a start, they've decided to study very simple kind of graph — a chain. A chain consists of N vertices, v1, v2,..., vN, and N-1 edges, connecting v1 with v2, v2 with v3,..., vN-1 with vN.

Given a position in this game, and assuming both players play optimally, who will win?

Input
The first line of input contains the integer N, .

The second line of input describes the current position. It contains N digits without spaces. ith digit describes the color of vertex vi: 0 — uncolored, 1 — black, 2 — white. No two vertices of the same color are adjacent.

Output
On the only line of output, print "FIRST" (without quotes) if the player moving first in that position wins the game, and "SECOND" (without quotes) otherwise.

Example(s)
sample input
sample output
5
00100
SECOND

sample input
sample output
4
1020
FIRST

=================
