test.cpp

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <numeric>

using namespace std;

const int MAXN = 10000005;

vector<int> min_prime(MAXN);
vector<int> primes;
vector<int> grundy;

void sieve(int max_n) {
    iota(min_prime.begin(), min_prime.begin() + max_n + 1, 0);
    
    for (int i = 2; i <= max_n; i++) {
        if (min_prime[i] == i) {
            primes.push_back(i);
        }
        for (int p : primes) {
            long long prod = (long long)i * p;
            if (prod > max_n) break;
            min_prime[prod] = p;
            if (i % p == 0) break;
        }
    }
}

void compute_grundy(int max_n) {
    grundy.resize(max_n + 1);
    grundy[1] = 0; // Base case: no moves from 1
    
    for (int u = 2; u <= max_n; u++) {
        set<int> reachable_grundy;
        
        // Move 1: Divide by prime factors
        int tmp = u;
        while (tmp > 1) {
            int p = min_prime[tmp];
            int v = u / p;
            reachable_grundy.insert(grundy[v]);
            while (tmp % p == 0) {
                tmp /= p;
            }
        }
        
        // Move 2: Multiply by primes
        for (int p : primes) {
            long long v = (long long)u * p;
            if (v > max_n) break;
            reachable_grundy.insert(grundy[(int)v]);
        }
        
        // Compute MEX (minimal excludant)
        int mex = 0;
        while (reachable_grundy.count(mex)) {
            mex++;
        }
        grundy[u] = mex;
    }
}

int main() {
    
    int t;
    cout << "Enter number of test cases: ";
    cin >> t;
    
    vector<int> queries(t);
    int max_n = 0;
    for (int i = 0; i < t; i++) {
        cin >> queries[i];
        max_n = max(max_n, queries[i]);
    }
    
    sieve(max_n);
    compute_grundy(max_n);
    
    for (int n : queries) {
        int winning_move = -1;
        
        // Find first even number with Grundy number 0
        for (int start = 2; start <= n; start += 2) {
            if (grundy[start] == 0) {
                winning_move = start;
                break;
            }
        }
        
        if (winning_move != -1) {
            cout << "first " << winning_move << "\n";
        } else {
            cout << "second\n";
        }
    }
    
    return 0;
}