#include using namespace std; using i8 = int8_t; using i16 = int16_t; using i32 = int32_t; using i64 = int64_t; using u8 = uint8_t; using u16 = uint16_t; using u32 = uint32_t; using u64 = uint64_t; using f32 = float; using f64 = double; using vi32 = std::vector; using vu32 = std::vector; using vf32 = std::vector; using vi64 = std::vector; using vu64 = std::vector; using vf64 = std::vector; using vvi32 = std::vector; using vvu32 = std::vector; using vvf32 = std::vector; using vvi64 = std::vector; using vvu64 = std::vector; using vvf64 = std::vector; using pi32 = std::pair; using pu32 = std::pair; using pf32 = std::pair; using pi64 = std::pair; using pu64 = std::pair; using pf64 = std::pair; #define ALL(obj) (obj).begin(),(obj).end() #define RALL(obj) ((obj).rbegin(),(obj).rend()) #define SZ(obj) ((i32)(obj).size()) #define EACH(it,o) for(auto it=(o).begin();it!=(o).end();++it) #define IN(l,n,r) ((l)<=(n) && (n)<(r)) #define UNIQUE(obj) (obj).erase(std::unique(ALL(obj)),(obj).end()) #define CLR(ar,val) memset(ar, val, sizeof(ar)) #define FOR(i,a,b) for(i32 i=(i32)(a); i<(i32)(b); i++) #define RFOR(i,a,b) for(i32 i=(i32)(b)-1;i>=(i32)(a);--i) #define REP(i,n) FOR(i,0,n) #define RREP(i,n) RFOR(i,0,n) #define PRINT(n) cout << (n) <<"\n"; #define cauto const auto& #define mp make_pair #define pb push_back const i32 INF = 0x3F3F3F3F; const i64 INF64 = 0x3F3F3F3F3F3F3F3F; const f64 EPS = 1e-8; const i32 MOD = 1000000007; static const f64 PI = 3.1415926535897932; static const f64 NAPIER = 2.7182818284590452; const char alphabetl[26] = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'}; const char alphabetu[26] = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'}; i32 dx[4] = {1, 0, -1, 0}; i32 dy[4] = {0, 1, 0, -1}; template inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); } template inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); } i64 BIT_COUNT_ONES(i64 x) { return __builtin_popcountll(x); } i64 BIT_COUNT_ZEROS(i64 x) { return 64 - BIT_COUNT_ONES(x); } //gcd(a, b) = a * x + b * y i64 extgcd(i64 a, i64 b, i64 &x, i64 &y) { i64 d = a; if(b != 0) { d = extgcd(b, a % b, y, x); y -= (a / b) * x; } else { x = 1; y = 0; } return d; } std::vector convert_base(i64 x, i64 b) { std::vector ret; i64 t = 1, k = abs(b); while (x) { ret.emplace_back((x * t) % k); if (ret.back() < 0) ret.back() += k; x -= ret.back() * t; x /= k; t *= b / k; } if (ret.empty()) ret.emplace_back(0); std::reverse(ALL(ret)); return ret; } std::vector prime_table(i32 n) { std::vector prime(n + 1, true); if(n >= 0) prime[0] = false; if(n >= 1) prime[1] = false; for(i32 i = 2; i * i <= n; i++) { if(!prime[i]) continue; for(i32 j = i + i; j <= n; j += i) { prime[j] = false; } } return prime; } //a ^ x === b (mod p) i64 mod_log(i64 a, i64 b, i64 p) { i64 ok = p, ng = -1; while(ok - ng > 1) { auto mid = (ok + ng) / 2; if (mid * mid >= p) ok = mid; else ng = mid; } std::unordered_map baby; baby.reserve(ok); i64 factor = 1; for (i64 i = 0, e = b; i < ok; i++) { baby[e] = i; (factor *= a) %= p; (e *= a) %= p; } for (i64 i = 1, e = factor; i <= ok; i++) { auto it = baby.find(e); if (it != baby.end()) return i * ok - it -> second; (e *= factor) %= p; } return -1; } //input pair tuple vector template std::istream& operator >> (std::istream& is,std::pair& p){is>>p.first>>p.second;return is;} template std::istream& operator >> (std::istream& is,std::tuple& t){is >> std::get<0>(t);return is;} template std::istream& operator >> (std::istream& is,std::tuple& t){is >> std::get<0>(t) >> std::get<1>(t);return is;} template std::istream& operator >> (std::istream& is,std::tuple& t){is >>std::get<0>(t)>>std::get<1>(t)>>std::get<2>(t);return is;} template std::istream& operator >> (std::istream& is,std::tuple& t){is >> std::get<0>(t)>>std::get<1>(t)>>std::get<2>(t)>>std::get<3>(t);return is;} template std::istream& operator >> (std::istream& is, const std::tuple& t){is >> std::get<0>(t) >> std::get<1>(t) >> std::get<2>(t) >> std::get<3>(t) >> std::get<4>(t);return is;} template std::istream& operator >> (std::istream& is, const std::tuple& t){is >> std::get<0>(t) >> std::get<1>(t) >> std::get<2>(t) >> std::get<3>(t) >> std::get<4>(t) >> std::get<5>(t);return is;} template std::istream& operator >> (std::istream& is, const std::tuple& t){is >> std::get<0>(t) >> std::get<1>(t) >> std::get<2>(t) >> std::get<3>(t) >> std::get<4>(t) >> std::get<5>(t) >> std::get<6>(t);return is;} template std::istream& operator >> (std::istream& is,std::vector& as){REP(i,SZ(as))is >>as[i];return is;} //output set pair map tuple vector template std::ostream& operator << (std::ostream& os, const std::set& ss){for(auto a:ss){if(a!=ss.begin())os<<" "; os< std::ostream& operator << (std::ostream& os, const std::pair& p){os< std::ostream& operator << (std::ostream& os, const std::map& m){bool isF=true;for(auto& p:m){if(!isF)os< std::ostream& operator << (std::ostream& os, const std::tuple& t){os << std::get<0>(t);return os;} template std::ostream& operator << (std::ostream& os, const std::tuple& t){os << std::get<0>(t)<<" "<(t);return os;} template std::ostream& operator << (std::ostream& os, const std::tuple& t){os << std::get<0>(t)<<" "<(t)<<" "<(t);return os;} template std::ostream& operator << (std::ostream& os, const std::tuple& t){os << std::get<0>(t)<<" "<(t)<<" "<(t)<<" "<(t);return os;} template std::ostream& operator << (std::ostream& os, const std::tuple& t){os << std::get<0>(t)<<" "<(t)<<" "<(t)<<" "<(t)<<" "<(t);return os;} template std::ostream& operator << (std::ostream& os, const std::tuple& t){os << std::get<0>(t)<<" "<(t)<<" "<(t)<<" "<(t)<<" "<(t)<<" "<(t);return os;} template std::ostream& operator << (std::ostream& os, const std::tuple& t){os << std::get<0>(t)<<" "<(t)<<" "<(t)<<" "<(t)<<" "<(t)<<" "<(t)<<" "<(t);return os;} template std::ostream& operator << (std::ostream& os, const std::vector& as){REP(i,as.size()){if(i!=0)os<<" "; os< std::ostream& operator << (std::ostream& os, const std::vector>& as){REP(i,SZ(as)){if(i!=0)os<> N; bool dp[10010]; dp[0] = dp[1] = true; auto prime = prime_table(N); vi32 P; for (i32 i = 2; i <= N; i++) if (prime[i]) P.pb(i); for (i32 i = 2; i <= N; i++) { if (!dp[i]) { for (i32 j = 0; j < SZ(P); j++) { if (i + P[j] > N) break; dp[i+P[j]] = true; } } } if (dp[N]) cout << "Win" << endl; else cout << "Lose" << endl; }