use std::io::{self, Read}; pub struct SievePrimes { sieve: Vec, current: usize, } impl SievePrimes { pub fn new(max: u32) -> SievePrimes { let mut sieve = vec![true; max as usize + 1]; sieve[0] = false; sieve[1] = false; SievePrimes { sieve, current: 1 } } } impl Iterator for SievePrimes { type Item = u32; fn next(&mut self) -> Option { loop { self.current += 1; if self.current >= self.sieve.len() || self.sieve[self.current] { break; } } if self.current < self.sieve.len() { if self.current * self.current <= self.sieve.len() { for i in (self.current..self.sieve.len()) .step_by(self.current) .skip(1) { self.sieve[i] = false; } } Some(self.current as u32) } else { None } } } #[derive(Debug)] struct Input { n: usize, } fn next_token(cin_lock: &mut io::StdinLock) -> String { cin_lock .by_ref() .bytes() .map(|c| c.unwrap() as char) .skip_while(|c| c.is_whitespace()) .take_while(|c| !c.is_whitespace()) .collect::() } fn read_input(cin_lock: &mut io::StdinLock) -> Input { Input { n: next_token(cin_lock).parse().unwrap(), } } fn can_win(n: usize) -> bool { let primes = SievePrimes::new(n as u32).collect::>(); let mut win = vec![false; n + 1]; // 非素数。ここに来る直前の手を負けとするため、この2つは勝利扱いにする win[0] = true; win[1] = true; for i in 2..=n { for &p in primes.iter().filter(|&&p| p as usize <= i) { if !win[i - p as usize] { win[i] = true; } } } win[n] } fn solve(input: Input, _cin_lock: &mut io::StdinLock) { println!("{}", if can_win(input.n) { "Win" } else { "Lose" }); } fn main() { let cin = io::stdin(); let mut cin_lock = cin.lock(); let input = read_input(&mut cin_lock); solve(input, &mut cin_lock); }