fn get_primes(n: usize) -> Vec { let mut flgs: Vec = vec![true; n+1]; flgs[0] = false; flgs[1] = false; if n < 2 { return vec![]; } let lim = (n as f64).sqrt().ceil() as usize + 1; for i in 2..=lim { if !flgs[i] { continue; } for j in i..=n/i { flgs[i*j] = false; } } flgs.iter().enumerate().filter(|pair| *pair.1).map(|pair| pair.0).collect() } fn main() { //TODO let mut n = String::new(); std::io::stdin().read_line(&mut n).ok(); let n: usize = n.trim().parse().unwrap(); let primes: Vec = get_primes(n); let mut result: Vec> = vec![None; n+1]; result[2] = Some(0); if n > 2 { result[3] = Some(0); } for i in 4..=n { let mut temp: Vec = vec![]; for p in primes.iter() { if *p > i - 2 { break; } if temp.contains(&p) { continue; } temp.push(result[i - p].unwrap()); } temp.sort(); let mut flg = false; for j in 0..temp.len() { if j == temp[j] { continue; } flg = true; result[i] = Some(j); break; } if !flg { result[i] = Some(temp.len()); } } println!("{}", if result[n] == Some(0) { "Lose" } else { "Win" }); }