# URL: https://yukicoder.me/problems/no/7 import algorithm, bitops, sequtils, strutils, sugar proc bsearch[T](min, max: T, cmp: proc(x: T): bool): T = var tmin = min tmax = max while tmax-tmin > 1: var mid = (tmin+tmax) div 2 if cmp(mid): tmin = mid else: tmax = mid if cmp(tmax): tmax elif cmp(tmin): tmin else: tmin-1 proc nsqrt[T](n: T): T = if n <= 1: return n var m = T(1) shl (n.fastLog2 div 2 + 1) bsearch(T(1), m, (x) => x*x <= n) proc primes(n: int): seq[int] = var sieve = newSeqWith((n+1) div 2, true) for p in 1..((n.nsqrt-1) div 2): if sieve[p]: for q in countup(p*3+1, (n+1) div 2, p*2+1): sieve[q] = false result = newSeq[int](0) for p, b in sieve: if b: result.add(p*2+1) result[0] = 2 var n = stdin.readline.parseInt grundy = newSeq[int](n+1) p = primes(n) for i in 4..n: var m = newSeq[bool](n+1) for pi in p: if i-pi < 2: break m[grundy[i-pi]] = true grundy[i] = m.find(false) echo if grundy[n] > 0: "Win" else: "Lose"