<|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.

### 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 (detailed comments)

```cpp
#include <bits/stdc++.h>
using namespace std;

/*
  Grundy values for a zero segment of length len, depending on boundary types:
  - diff: both neighbors exist and have different colors -> 0
  - match: both neighbors exist and have same color -> 1 (for len >= 1)
  - boundary: exactly one neighbor exists (segment touches an end) -> len
  - free: no neighbors exist (whole chain is zeros) -> len % 2
*/

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

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

    int n;
    string s;
    cin >> n >> s;

    int xor_sum = 0;

    // Scan the string and extract maximal contiguous blocks of '0'
    for (int i = 0; i < n; ) {
        if (s[i] != '0') {
            ++i;
            continue;
        }

        // Found a zero segment starting at i
        int start = i;
        while (i < n && s[i] == '0') ++i;
        int len = i - start; // segment is [start, i)

        // Determine boundary colors; use 0 as sentinel for "missing"
        char left  = (start > 0) ? s[start - 1] : 0;
        char right = (i < n)     ? s[i]         : 0;

        int sg;
        if (left == 0 && right == 0) {
            // Segment touches both ends => entire chain is zeros
            sg = sg_free(len);
        } else if (left == 0 || right == 0) {
            // Segment touches exactly one end
            sg = sg_boundary(len);
        } else if (left == right) {
            // Both neighbors exist and have the same color
            sg = sg_match(len);
        } else {
            // Both neighbors exist and have different colors
            sg = sg_diff(len);
        }

        xor_sum ^= sg;
    }

    cout << (xor_sum != 0 ? "FIRST" : "SECOND") << "\n";
    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()
```

