#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; #define FOR(i,a,b) for(ll i=(a);i<(b);++i) #define ALL(v) (v).begin(), (v).end() #define p(s) cout<<(s)< void vprint(T &V){ for(auto v : V){ cout << v << " "; } cout << endl; } const int N_MAX = 10010; bool is_prime[N_MAX]; // エラトステネスのふるい void Eratosthenes(){ FOR(i, 0, N_MAX){ is_prime[i] = true; } is_prime[0] = false; is_prime[1] = false; FOR(i, 2, N_MAX){ if(is_prime[i]==1){ int p = i; int step_p = p; // それの倍数を消していく while(p < N_MAX){ p += step_p; if(p> N; Eratosthenes(); vector primes; FOR(i, 0, N+1){ if(is_prime[i]){ primes.push_back(i); } } vector dp(N+1, false); // can win ? FOR(i, 4, 11){ dp[i] = true; } FOR(i, 11, N+1){ for(ll prime : primes){ ll rest = i - prime; if(rest<=1){ break; } // 負けを押し付けられる if(dp[rest]==false){ dp[i] = true; break; } } } if(dp[N]){ p("Win"); }else{ p("Lose"); } return 0; }