1. Abridged Problem Statement
You have a heap of N matches. Two players alternate removing matches, where on each move a player may take exactly 1 or one of the values P₁,…,Pₘ (each between 2 and 9). The player who takes the last match loses. Given N (up to 10⁹) and the set {P₁,…,Pₘ}, determine which player has a forced win under perfect play.

2. Detailed Editorial

Game reformulation
- This is a subtraction (take-away) game under the misère rule: the player taking the last object loses.
- Let S = {1, P₁, P₂, …, Pₘ}. Moves from a heap of size i are to i − s for any s∈S with s ≤ i.

Dynamic programming
- Define dp[i] = 1 if the position with i matches is winning for the player to move, and dp[i] = 0 if it is losing.
- Base: dp[0] = 1, because if there are 0 matches on your turn, your opponent just took the last one and lost — so you "win" by default.
- dp[i] = 1 if there exists an s∈S, s ≤ i, such that transitioning to i−s yields a losing position dp[i−s] = 0. Otherwise dp[i] = 0.

Misère subtlety
- In normal play you win by taking the last object; in misère play you lose by taking the last object. Because we include the move of size 1 and set dp[0]=1, dp[1]=0, the simple DP above handles the misère condition correctly.

Periodicity for large N
- Since all allowed moves are at most 9, dp[i] depends only on the previous 10 values. Therefore the sequence dp[0], dp[1], … is eventually periodic with period at most 2¹⁰ (the number of distinct bit-patterns of length 10).
- We compute dp[i] and maintain a 10-bit "state" encoding which of dp[i],dp[i−1],…,dp[i−9] are winning. As soon as a state repeats at two different i's, we detect a cycle.
- Let first_i be the previous occurrence of the same state at index i; cycle_length = i − first_i. For N ≥ i, dp[N] = dp[first_i + ((N−i) mod cycle_length)], which the code computes as dp[i − cycle_length + ((n−i) mod cycle_length)].

Complexity
- We only need to compute up to when a cycle is found, which is at most a few thousand steps (≤ around 1024 states). Each step checks up to m+1 moves (≤9). Overall O(1024·9) per test case.

3. C++ Solution
```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;
}
```

4. Python Solution
```python
import sys

def winner(n, moves):
    # moves: sorted list of allowed removal sizes, including 1
    # We store dp up to detection of cycle in a dict of states.
    # dp[i] = 1 if winning, 0 if losing for the player to move at size i.
    # Base: dp[0] = 1 (opponent just lost by taking last), dp[1] = 0 (only move loses).

    # Maximum window for cycle detection: 10 bits -> at most 1024 distinct states
    pos_of_state = {}   # state_mask -> first index i
    dp = [1, 0]         # initial dp[0], dp[1]

    # If n <= 1, we already know the answer
    if n <= 1:
        return dp[n]

    limit = min(n, (1 << 13) - 1)  # some safe upper limit to compute until cycle
    for i in range(2, limit + 1):
        # Compute 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]
        st = 0
        for b in range(10):
            if i - b < 0 or dp[i - b] == 1:
                st |= 1 << b

        if st not in pos_of_state:
            pos_of_state[st] = i
        else:
            # Cycle detected
            first_i = pos_of_state[st]
            cycle_len = i - first_i
            # Map n into the cycle
            idx = first_i + ((n - first_i) % cycle_len)
            return dp[idx]

    # If no cycle up to our limit, then dp[n] is known directly
    return dp[n]

def main():
    data = sys.stdin.read().strip().split()
    t = int(data[0])
    ptr = 1
    out = []
    for _ in range(t):
        n = int(data[ptr]); ptr += 1
        m = int(data[ptr]); ptr += 1
        p = list(map(int, data[ptr:ptr+m]))
        ptr += m
        # Always include removal of 1
        moves = sorted(set(p + [1]))
        w = winner(n, moves)
        out.append("FIRST PLAYER MUST WIN" if w else "SECOND PLAYER MUST WIN")
    print("\n".join(out))

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

5. Compressed Editorial
- Model the game as a misère subtraction game with moves S = {1, P₁,…,Pₘ}.
- dp[i] = winning iff ∃s∈S s.t. dp[i−s] is losing; dp[0]=1, dp[1]=0.
- Because S's maximum is ≤9, the sequence dp is eventually periodic with period ≤2¹⁰.
- Detect the cycle by hashing the last 10 dp bits into a state, record first occurrence, and when repeated, use modular arithmetic to find dp[N].
