import std.algorithm, std.array, std.container, std.range; import std.string, std.conv, std.math; import std.stdio, std.typecons; void main() { auto n = readln.chomp.to!int; auto primes = primes(n); primes.reverse(); auto memo = new Nullable!bool[n + 1]; auto r = dp(n, true, primes, memo); writeln(r ? "Win" : "Lose"); } bool dp(int n, bool turn, int[] primes, Nullable!bool[] memo) { bool winner_is_me; if (n == 0 || n == 1) { winner_is_me = true; } else if (!memo[n].isNull) { winner_is_me = memo[n]; } else { winner_is_me = primes .find!(a => a < n) .any!(p => dp(n - p, !turn, primes, memo) == turn); } memo[n] = winner_is_me; return !(winner_is_me ^ turn); } int[] primes(int n) { auto sieve = new bool[n + 1]; sieve.fill(true); auto max = sqrt(n.to!real).to!int; for (auto p = 2; p <= max; ++p) { if (sieve[p]) { for (auto q = p * 2; q <= n; q += p) { sieve[q] = false; } } } int[] r; for (auto p = 2; p <= n; ++p) { if (sieve[p]) { r ~= p; } } return r; }