use fio::*; struct BitSet { n: usize, arr: Vec, } impl BitSet { fn new(n: usize) -> Self { BitSet { n, arr: vec![0; n.div_ceil(64) + 1], // to prevent off-by-1 error, and fill with 0. } } fn set(&mut self, idx: usize, val: bool) { assert!((0..self.n).contains(&idx)); let (idx, rem) = (idx / 64, idx % 64); if val { self.arr[idx] |= 1u64 << rem; } else { self.arr[idx] &= !(1u64 << rem); } } fn get(&self, idx: usize) -> bool { assert!((0..self.n).contains(&idx)); let (idx, rem) = (idx / 64, idx % 64); (self.arr[idx] & (1u64 << rem)) != 0 } /// arr[s..t] ^= arr[u..v] fn rng_xor(&mut self, s: usize, t: usize, u: usize, v: usize) { assert!(s < t && t <= self.n && u < v && v <= self.n && t - s == v - u); let len = (v - u).div_ceil(64); if len == 0 { // no-op return; } let mut buf = vec![0u64; len + 1]; // to prevent off-by-1 error. // buf = arr[u..v] let rem = u % 64; if rem == 0 { for i in 0..len { buf[i] = self.arr[u / 64 + i]; } } else { for i in 0..len { buf[i] = (self.arr[u / 64 + i] >> rem) | (self.arr[u / 64 + i + 1] << (64 - rem)); } } // Ignore the last part if the last_block is not full. let last_block = (v - u) % 64; if last_block != 0 { buf[len - 1] &= (1u64 << last_block) - 1; } // arr[s..t] ^= buf let rem = s % 64; if rem == 0 { // the last part is filled with 0, so safe to XOR. for i in 0..len { self.arr[s / 64 + i] ^= buf[i]; } } else { self.arr[s / 64] ^= buf[0] << rem; for i in 1..=len { self.arr[s / 64 + i] ^= (buf[i - 1] >> (64 - rem)) | (buf[i] << rem); } } } } fn main() { let [n, s, x, y, z] = read_tuple::(); let mut bs = BitSet::new(n); let mut cur = s; bs.set(0, cur % 2 == 1); for i in 1..n { cur = (x * cur + y) % z; bs.set(i, cur % 2 == 1); } let q = read::(); for _ in 0..q { let [s, t, u, v] = read_tuple::(); bs.rng_xor(u - 1, v, s - 1, t); } for i in 0..n { print!("{}", if bs.get(i) { 'O' } else { 'E' }) } } mod fio { use std::{ cell::RefCell, convert::TryInto, fmt::Debug, io::{BufRead, BufWriter, StdinLock, StdoutLock, stdin, stdout}, str::FromStr, }; thread_local! { pub static STDIN: RefCell> = RefCell::new(stdin().lock()); pub static STDOUT: RefCell>> = RefCell::new(BufWriter::new(stdout().lock())); } #[allow(dead_code)] pub fn read() -> T where ::Err: Debug, { read_line().parse().unwrap() } #[allow(dead_code)] pub fn read_vec() -> Vec where ::Err: Debug, { read_line() .split_whitespace() .map(|x| x.parse().unwrap()) .collect() } #[allow(dead_code)] pub fn read_tuple() -> [T; N] where T: FromStr + Debug, ::Err: Debug, { read_vec::().try_into().unwrap() } /// whitespace at the end of the line is ignored pub fn read_line() -> String { let mut s = String::new(); STDIN.with(|cell| { cell.borrow_mut().read_line(&mut s).unwrap(); }); String::from_str(s.trim_end()).unwrap() } } #[macro_export] macro_rules! print { ($($t:tt)*) => { fio::STDOUT.with(|cell|{ use std::io::Write; write!(cell.borrow_mut(), $($t)*).unwrap() })}; } #[macro_export] macro_rules! println { ($($t:tt)*) => { fio::STDOUT.with(|cell| { use std::io::Write; writeln!(cell.borrow_mut(), $($t)*).unwrap() }) }; } #[macro_export] macro_rules! flush { () => { fio::STDOUT.with(|cell| { use std::io::Write; cell.borrow_mut().flush().unwrap() }); }; }