<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

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

<|response|>
## 1) Abridged problem statement (concise)

You are given a path graph (a chain) of **N** vertices. Each vertex is:

- `0` = uncolored
- `1` = black
- `2` = white

The current coloring is valid: **no two adjacent colored vertices share the same color**.

Two players alternate moves; on a move, a player colors any uncolored vertex black or white, but still must keep adjacent vertices different. If a player has no legal move, they lose.

Determine who wins with optimal play from the given position. Output `"FIRST"` if the next player wins, else `"SECOND"`.

---

## 2) Key observations

1. **Only neighbors matter on a path.**
   Coloring a vertex only depends on its immediate left/right neighbors.

2. **Colored vertices split the game into independent zero-blocks.**
   Consider maximal contiguous segments of `0`'s (uncolored vertices).
   Moves inside one segment cannot affect legality in another segment because the colored vertices between them are fixed "walls".

3. **Therefore this is a disjunctive sum of impartial subgames.**
   By the **Sprague–Grundy theorem**, the whole position is winning iff:
   \[
   SG_{total} = SG_1 \oplus SG_2 \oplus \cdots \oplus SG_k \neq 0
   \]
   where each \(SG_i\) is the Grundy number of one zero-segment.

4. **A zero-segment's Grundy number depends only on:**
   - its length `len`
   - the colors at its two boundaries (left neighbor and right neighbor), if they exist.

   There are 4 boundary types:

   | Type | Left boundary | Right boundary |
   |------|---------------|----------------|
   | free | none (end) | none (end) |
   | boundary | colored | none (end) OR none + colored |
   | match | colored `c` | colored same `c` |
   | diff | colored `1` | colored `2` (or vice versa) |

---

## 3) Full solution approach

### Step A: Split into maximal zero segments
Scan the string and extract each maximal block of consecutive `'0'` characters:
- segment = `s[l..r]` all zeros
- `len = r-l+1`

Determine boundary colors:
- `left = s[l-1]` if `l > 0`, else "missing"
- `right = s[r+1]` if `r+1 < N`, else "missing"

### Step B: Use closed-form Grundy values for each segment
For a segment of length `len`:

- **diff** (both sides colored and different):
  `SG = 0`

- **match** (both sides colored and equal):
  `SG = 1` if `len >= 1` else `0` (len won't be 0 in practice)

- **boundary** (exactly one side colored, other side is chain end):
  `SG = len`

- **free** (both sides are ends; i.e., whole chain is zeros):
  `SG = len % 2`

These formulas are the crucial pre-derived pattern for this game on a path. Naively computing SG via mex would be O(N^2); spotting the pattern from a small table makes it O(N).

### Step C: XOR all segment SG values
Initialize `xor_sum = 0`, and for each segment do:
`xor_sum ^= SG(segment)`

Finally:
- if `xor_sum != 0` → winning for next player → print `"FIRST"`
- else → losing for next player → print `"SECOND"`

### Complexity
- Single scan: **O(N)** time
- Constant extra memory: **O(1)**
- Fits easily in the constraints (very small time limit).

---

## 4) C++ implementation

```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;
}
```

---

## 5) Python implementation (detailed comments)

```python
import sys

def sg_match(length: int) -> int:
    # Both neighbors exist and are the same color.
    return 1 if length >= 1 else 0

def sg_diff(length: int) -> int:
    # Both neighbors exist and are different colors.
    return 0

def sg_boundary(length: int) -> int:
    # Exactly one side has a colored neighbor (segment touches an end).
    return length

def sg_free(length: int) -> int:
    # No colored neighbors on either side (whole chain is zeros).
    return length % 2

def solve() -> None:
    data = sys.stdin.read().strip().split()
    n = int(data[0])
    s = data[1]

    xor_sum = 0
    i = 0

    # Scan s and process maximal '0' segments
    while i < n:
        if s[i] != '0':
            i += 1
            continue

        start = i
        while i < n and s[i] == '0':
            i += 1
        length = i - start

        # Determine boundaries; None means "missing neighbor"
        left = s[start - 1] if start > 0 else None
        right = s[i] if i < n else None

        # Classify segment and compute its Grundy number
        if left is None and right is None:
            sg = sg_free(length)
        elif left is None or right is None:
            sg = sg_boundary(length)
        elif left == right:
            sg = sg_match(length)
        else:
            sg = sg_diff(length)

        xor_sum ^= sg

    sys.stdout.write("FIRST\n" if xor_sum != 0 else "SECOND\n")

if __name__ == "__main__":
    solve()
```
