use std::io::*; use std::str::FromStr; use utils::*; pub fn main() { let i = stdin(); let mut o = Vec::new(); run(i.lock(), &mut o); stdout().write_all(&o).unwrap(); } fn run(i: R, o: &mut W) { let mut i = CpReader::new(i); let seed = i.read::(); writeln!(o, "{}", solve(seed)).unwrap(); } struct Gen { x: u32, y: u32, z: u32, w: u32, } impl Gen { fn new(seed: u32) -> Self { Gen { x: seed, y: 1, z: 2, w: 3, } } fn next(&mut self) -> u32 { let t = self.x ^ (self.x << 11); self.x = self.y; self.y = self.z; self.z = self.w; self.w = (self.w ^ (self.w >> 19)) ^ (t ^ (t >> 8)); return self.w; } } fn solve(seed: u32) -> u32 { let mut ns = Vec::new(); let mut g = Gen::new(seed); for _ in 0..10000001 + 1 { ns.push(g.next()); } fn is_over_mid(ns: &[u32], mid: u32) -> bool { let mut c = 0; for &n in ns { if n <= mid { c += 1; } } c >= 5000001 } let mut low = 0; let mut high = u32::max_value(); while low < high { let mid = ((low as u64 + high as u64) / 2) as u32; if is_over_mid(&ns, mid) { high = mid; } else { low = mid + 1; } } low } mod utils { use super::*; pub struct CpReader { r: R, s: String, } impl CpReader { pub fn new(r: R) -> Self { CpReader { r: r, s: String::new(), } } pub fn read_line(&mut self) -> &str { self.s.clear(); self.r.read_line(&mut self.s).unwrap(); self.s.trim() } pub fn read(&mut self) -> T { self.read_line().parse().ok().unwrap() } } }