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

153. Playing with matches
time limit per test: 0.25 sec.
memory limit per test: 4096 KB
input: standard input
output: standard output



Little boy Petya plays a game with his friend. They have a heap that consists of N (1<=N<=10^9) matches. It is possible to take 1,P1,P2,...,Pm (2<=Pi<=9, 0<=m<=8) matches from the heap.
Players take matches from the heap one by one. The player who takes the last match looses. Petya proved that for any set of N and Pi one of players has winning strategy, i.e. set of rules driving to a victory independently of opponent's moves. You task is to discover who has this strategy.

Input
Input file consist of K test cases. Natural number K is written in the first line. Every test case describes one game: numbers N and M are written in first line of every test case, and second line contains sequence Pi. All numbers in then input are integer numbers. So, if K=2, then second and third lines describe first game and fourth and fifth lines describe second game.

Output
For each test case write in the output file phrase FIRST PLAYER MUST WIN if first player have winning strategy, and SECOND PLAYER MUST WIN therwise.

Sample test(s)

Input
1
5 3
2 3 5

Output
SECOND PLAYER MUST WIN
Author:	Andrew V. Lazarev
Resource:	Saratov Subregional School Team Contest, 2002
Date:	Spring, 2002

<|response|>
1. Abridged Problem Statement
You have a heap of N matches (1 ≤ N ≤ 10⁹). Two players alternate removing matches. On each move a player may take exactly 1 or one of the values P₁,…,Pₘ (each 2 ≤ Pᵢ ≤ 9). The player who takes the last match loses. Under perfect play, determine which player has a forced win.

Input: K test cases. For each test case, N and m, then m integers P₁…Pₘ.
Output: For each test case, print
  FIRST PLAYER MUST WIN
or
  SECOND PLAYER MUST WIN

2. Key Observations
- This is a subtraction game under the misère rule (last move loses).
- Let S = {1, P₁, P₂, …, Pₘ}. From a heap of size i you may move to i−s for any s∈S with s ≤ i.
- Define dp[i] = 1 if the position with i matches is winning for the player about to move, dp[i] = 0 if it is losing.
- Misère twist: normally taking the last wins; here it loses. If we set dp[0] = 1 (with 0 matches your opponent just took last and lost, so you "win" by default) and dp[1] = 0 (if you take the single match, you lose immediately), the standard DP recurrence still applies:
  dp[i] = 1 if there exists s in S, s ≤ i, such that dp[i−s] = 0; otherwise dp[i] = 0.
- Since all moves s ≤ 9, dp[i] depends only on dp[i−1]…dp[i−9]. Therefore the sequence {dp[i]} is eventually periodic with period at most 2¹⁰ = 1024. We can detect the cycle by hashing the last 10 dp-values into a 10-bit integer "state."

3. Full Solution Approach
For each test case:
a. Read N, m and the list P₁…Pₘ. Append 1 to the list, sort and deduplicate to get moves S.
b. Prepare a dp[] vector and a pos_of_state array of size 1<<10 initialized to −1.
c. Set dp[0] = 1, dp[1] = 0.
d. Iterate i = 2,3,… up to N (the buffer is bounded by 1<<13 since a cycle is always found early), computing dp[i]:
  - dp[i] = 1 if ∃ s∈S, s ≤ i, such that dp[i−s] = 0; else dp[i] = 0.
  - Build the 10-bit state where bit k is set if dp[i−k]==1 or (i−k)<0.
  - If pos_of_state[state] == −1, record pos_of_state[state] = i. Else a cycle is detected:
   cycle_length = i − pos_of_state[state]; the answer is dp[i − cycle_length + ((N − i) mod cycle_length)].
e. If no cycle was detected up to N, the answer is dp[N].
f. Output "FIRST PLAYER MUST WIN" if the answer is 1, otherwise "SECOND PLAYER MUST WIN."

Time complexity per test is O(Period × |S|), with Period ≤ 1024 and |S| ≤ 9.

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, m;
vector<int> p;

void read() {
    cin >> n >> m;
    p.resize(m);
    for(int i = 0; i < m; i++) {
        cin >> p[i];
    }
    p.push_back(1);
}

void solve() {
    // This is a losing-last-match (misere) take-away game: dp[i] is 1 if the
    // player to move with i matches wins. Position i wins if some allowed move
    // x leads to a losing position dp[i - x] == 0; dp[0] = 1 encodes that
    // facing 0 matches means the opponent just took the last and lost. Since
    // moves take at most 9 matches, dp[i] depends only on the previous 10
    // values, so the sequence is eventually periodic. We pack the last 10
    // outcomes into a 10-bit state and record the first index each state
    // appears; on a repeat we know the cycle length and jump straight to the
    // equivalent index for n via modular arithmetic instead of iterating up to
    // 10^9.

    sort(p.begin(), p.end());
    p.erase(unique(p.begin(), p.end()), p.end());

    vector<int> pos_of_state(1 << 10, -1);

    vector<int> dp(min(1 << 13, n + 1), 0);
    dp[1] = 0;
    dp[0] = 1;

    int ans = -1;
    for(int i = 2; i <= n; i++) {
        for(int x: p) {
            if(x > i) {
                break;
            }
            if(dp[i - x] == 0) {
                dp[i] = 1;
                break;
            }
        }

        int state = 0;
        for(int prv = 0; prv < 10; prv++) {
            if(i - prv < 0 || dp[i - prv] == 1) {
                state |= (1 << prv);
            }
        }

        if(pos_of_state[state] == -1) {
            pos_of_state[state] = i;
        } else {
            int cycle_length = i - pos_of_state[state];
            int need = (n - i) % cycle_length;

            ans = dp[i - cycle_length + need];
            break;
        }
    }

    if(ans == -1) {
        ans = dp[n];
    }

    cout << (ans ? "FIRST PLAYER MUST WIN" : "SECOND PLAYER MUST WIN") << '\n';
}

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 with Detailed Comments
```python
import sys

def winner(N, moves):
    # moves: sorted list of allowed removals including 1
    # dp[i] = 1 if winning, 0 if losing for the player to move
    # Base: dp[0]=1, dp[1]=0 under misère rule
    dp = [1, 0]
    pos_of_state = {}  # maps 10-bit state -> first index it appeared

    if N <= 1:
        return dp[N]

    LIMIT = (1 << 13) - 1
    max_compute = min(N, LIMIT)

    for i in range(2, max_compute + 1):
        # Determine dp[i]
        win = 0
        for s in moves:
            if s > i:
                break
            if dp[i - s] == 0:
                win = 1
                break
        dp.append(win)

        # Build 10-bit signature of dp[i], dp[i-1], …, dp[i-9]
        state = 0
        for b in range(10):
            if i - b < 0 or dp[i - b] == 1:
                state |= (1 << b)

        if state not in pos_of_state:
            pos_of_state[state] = i
        else:
            # Cycle detected
            first_i = pos_of_state[state]
            cycle_len = i - first_i
            idx = first_i + ((N - first_i) % cycle_len)
            return dp[idx]

    # No cycle up to max_compute, so dp[N] is known directly
    return dp[N]

def main():
    data = sys.stdin.read().split()
    it = iter(data)
    K = int(next(it))
    out = []

    for _ in range(K):
        N = int(next(it))
        m = int(next(it))
        p = [int(next(it)) for _ in range(m)]
        # Always include removal of 1
        moves = sorted(set(p + [1]))
        w = winner(N, moves)
        if w:
            out.append("FIRST PLAYER MUST WIN")
        else:
            out.append("SECOND PLAYER MUST WIN")

    print("\n".join(out))

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