#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define rep(i, n) for(int i = 0; i < (n); i++) #define per(i, n) for(int i = (n) - 1; i >= 0; i--) using ll = long long; #define vi vector #define vvi vector #define vl vector #define pii pair #define pll pair #define all(a) (a).begin(), (a).end() #define rall(a) (a).rbegin(), (a).rend() constexpr int mod = 1000000007; using namespace std; template bool chmax(T &a, const U &b){ return a < b ? (a = b, 1) : 0; } template bool chmin(T &a, const U &b){ return a > b ? (a = b, 1) : 0; } struct range_eratosthenes { private: ll L,R,M; static constexpr int Max_range = 1000010; //10^6 bitset small, large; public: range_eratosthenes(ll L, ll R) : L(L), R(R), M(sqrt(R)+1){ assert(M <= Max_range && R - L <= Max_range); for(ll i = 2; i < M; i++){ if(small[i]) continue; for(ll j = i+i; j < M; j += i) small[j] = 1; for(ll j = max(2LL, (L+i-1)/i)*i; j < R; j += i) large[j - L] = 1; } } bool is_prime(const ll &n) const{ assert(L <= n && n < R); return !large[n - L]; } }; int main(){ int n; cin >> n; range_eratosthenes ss(2, n+1); vi s; for(int i = 2; i <= n; i++) if(ss.is_prime(i)) s.push_back(i); vi dp(n+1, -1); dp[0] = dp[1] = 1; // win for(int i = 2; i <= n; i++){ bool win = false; for(int x : s){ if(i-x < 0 || win) break; if(!dp[i-x]) win = true; } dp[i] = win; } if(dp[n]) cout << "Win\n"; else cout << "Lose\n"; }