#include #include #include #include #include #include constexpr int UNDEF = -1; typedef std::set GrundySet; // 所与の整数(> 1)未満の素数を、Eratosthenesの篩により列挙するる const std::vector sieve_of_eratosthenes(const int& end) { assert(end > 1); std::vector is_prime(end, true); std::vector primes; is_prime[0] = false; is_prime[1] = false; for (auto i = 2; i < end; i++) { if (is_prime[i]) { primes.push_back(i); for (auto j = 2 * i; j < end; j += i) { is_prime[j] = false; } } } return primes; } // 所与の集合に含まれない最小の非負整数を求める // 参考 http://solorab.net/blog/2015/12/19/srm-676-med/ int mex(const GrundySet& s) { int m = 0; for (const auto& x : s) { if (x == m) { m++; } else { break; } } return m; } // 渡された数字がNであるという状態のGrundy数を計算する int compute_grundy_number(int n) { std::vector gs(std::max(n, 3) + 1, UNDEF); auto primes = sieve_of_eratosthenes(n + 1); // 渡された数字が2, 3であれば、負ける gs[2] = 0; gs[3] = 0; for (auto i = 4; i <= n; i++) { GrundySet next_gs; for (const auto& prime : primes) { auto cand = i - prime; if (cand < 2) { break; } next_gs.insert(gs[cand]); } gs[i] = mex(next_gs); } return gs[n]; } int main() { std::cin.tie(nullptr); std::ios::sync_with_stdio(false); int n; std::cin >> n; auto g = compute_grundy_number(n); std::cout << (g > 0 ? "Win" : "Lose") << std::endl; return EXIT_SUCCESS; }