heh
tmp
| -rw-r--r-- | Cargo.toml | 2 | ||||
| -rw-r--r-- | bruh.rs | 1487 | ||||
| -rw-r--r-- | src/inp.txt | 1006 | ||||
| -rw-r--r-- | src/main.rs | 175 |
4 files changed, 1563 insertions, 1107 deletions
@@ -9,7 +9,9 @@ edition = "2021" atools = "0.1.5" # hinted = "0.0.1" itertools = "0.12.0" +logos = "0.14.3" memchr = "2.6.4" +regex = "1.11.1" # radsort = "0.1.1" rustc-hash = { version = "2.1.0", features = ["nightly"] } [profile.release] @@ -0,0 +1,1487 @@ +#![allow(warnings)] +#![feature( + slice_swap_unchecked, + generic_const_exprs, + iter_array_chunks, + get_many_mut, + maybe_uninit_uninit_array, + iter_collect_into, + let_chains, + anonymous_lifetime_in_impl_trait, + array_windows, + slice_take, + test, + slice_as_chunks, + array_chunks, + slice_split_once, + core_intrinsics +)] + +mod util { + #![allow(non_snake_case, unused_macros)] + + use rustc_hash::FxHashMap as HashMap; + use rustc_hash::FxHashSet as HashSet; + use std::{ + cmp::Reverse, + collections::{hash_map::Entry, BinaryHeap}, + fmt::{Debug, Display, Write}, + hash::Hash, + mem::swap, + ops::RangeInclusive, + str::FromStr, + }; + + pub mod prelude { + #[allow(unused_imports)] + pub(crate) use super::{bits, dang, leek, mat, shucks, C}; + pub use super::{ + even, gcd, gt, l, lcm, lt, pa, r, rand, reading, reading::Ext, sort, Dir, FilterBy, + FilterBy3, GreekTools, IntoCombinations, IntoLines, IterͶ, NumTupleIterTools, + ParseIter, Printable, Skip, TakeLine, TupleIterTools2, TupleIterTools2R, + TupleIterTools3, TupleUtils, UnifiedTupleUtils, UnsoundUtilities, Widen, Ͷ, Α, Κ, Λ, Μ, + }; + pub use itertools::izip; + pub use itertools::Itertools; + pub use rustc_hash::FxHashMap as HashMap; + pub use rustc_hash::FxHashSet as HashSet; + pub use std::{ + cmp::Ordering::*, + cmp::{max, min}, + collections::{hash_map::Entry, VecDeque}, + fmt::{Debug, Display}, + hint::black_box as boxd, + io::{self, Read, Write}, + iter, + mem::{replace as rplc, swap, transmute as rint}, + ops::Range, + }; + } + + macro_rules! C { + ($obj:ident.$what:ident$($tt:tt)+) => {{ + let x = &mut $obj.$what; + C!( x$($tt)+ ) + }}; + (&$buf:ident[$n:expr]) => {{ + #[allow(unused_unsafe)] + unsafe { + $buf.get_unchecked($n) + } + }}; + ($buf:ident[$n:expr]) => {{ + #[allow(unused_unsafe)] + *unsafe { + $buf.get_unchecked($n) + } + }}; + (&mut $buf:ident[$n:expr]) => {{ + #[allow(unused_unsafe)] + unsafe { + $buf.get_unchecked_mut($n) + } + }}; + ($buf:ident[$a:expr] = $rbuf:ident[$b:expr]) => { + *unsafe { $buf.get_unchecked_mut($a) } = unsafe { *$rbuf.get_unchecked($b) } + }; + ($buf:ident[$n:expr] = $e:expr) => { + *unsafe { $buf.get_unchecked_mut($n) } = $e + }; + ($buf:ident[$a:expr][$b:expr]) => { + unsafe { *$buf.get_unchecked($a).get_unchecked($b) } + }; + ($buf:ident[$a:expr][$b:expr] = $rbuf:ident[$ra:expr]) => { + *unsafe { $buf.get_unchecked_mut($a).get_unchecked_mut($b) } = + unsafe { *$rbuf.get_unchecked($ra) } + }; + ($buf:ident[$a:expr][$b:expr] = $rbuf:ident[$ra:expr][$rb:expr]) => { + *unsafe { $buf.get_unchecked_mut($a).get_unchecked_mut($b) } = + unsafe { *$rbuf.get_unchecked($ra).get_unchecked($rb) } + }; + ($buf:ident[$a:expr][$b:expr] = $c:expr) => {{ + #[allow(unused_unsafe)] + { + *unsafe { $buf.get_unchecked_mut($a).get_unchecked_mut($b) } = unsafe { $c } + } + }}; +} + pub(crate) use C; + + macro_rules! shucks { + () => { + if cfg!(debug_assertions) { + unreachable!(); + } else { + unsafe { std::hint::unreachable_unchecked() } + } + }; + ($fmt:literal $(, $args:expr)* $(,)?) => { + if cfg!(debug_assertions) { + unreachable!($fmt $(, $args)*); + } else { + unsafe { std::hint::unreachable_unchecked() } + } + }; + (if $x:expr) => { + if $x { + if cfg!(debug_assertions) { + unreachable!(); + } else { + unsafe { std::hint::unreachable_unchecked() } + } + } + }; +} + pub(crate) use shucks; + + macro_rules! dang { + () => { + panic!() + }; + } + pub(crate) use dang; + + macro_rules! leek { + ($($allocation:ident)+) => { + $(std::mem::forget($allocation);)+ + }; +} + pub(crate) use leek; + + macro_rules! mat { + ($thing:ident { $($what:pat => $b:expr,)+ }) => { + match $thing { $($what => { $b })+ _ => shucks!() } + }; +} + pub(crate) use mat; + + #[cfg(target_feature = "avx2")] + unsafe fn count_avx<const N: usize>(hay: &[u8; N], needle: u8) -> usize { + use std::arch::x86_64::*; + let find = _mm256_set1_epi8(needle as i8); + let mut counts = _mm256_setzero_si256(); + for i in 0..(N / 32) { + counts = _mm256_sub_epi8( + counts, + _mm256_cmpeq_epi8( + _mm256_loadu_si256(hay.as_ptr().add(i * 32) as *const _), + find, + ), + ); + } + const MASK: [u8; 64] = [ + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, + 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, + ]; + counts = _mm256_sub_epi8( + counts, + _mm256_and_si256( + _mm256_cmpeq_epi8( + _mm256_loadu_si256(hay.as_ptr().add(N - 32) as *const _), + find, + ), + _mm256_loadu_si256(MASK.as_ptr().add(N % 32) as *const _), + ), + ); + + let sums = _mm256_sad_epu8(counts, _mm256_setzero_si256()); + (_mm256_extract_epi64(sums, 0) + + _mm256_extract_epi64(sums, 1) + + _mm256_extract_epi64(sums, 2) + + _mm256_extract_epi64(sums, 3)) as usize + } + + pub fn count<const N: usize>(hay: &[u8; N], what: u8) -> usize { + #[cfg(target_feature = "avx2")] + return unsafe { count_avx(hay, what) }; + #[cfg(not(target_feature = "avx2"))] + hay.iter().filter(|&&x| x == what).count() + } + + pub fn lcm(n: impl IntoIterator<Item = u64>) -> u64 { + let mut x = n.into_iter(); + let mut lcm = x.by_ref().next().expect("cannot compute LCM of 0 numbers"); + let mut gcd; + for x in x { + gcd = crate::util::gcd(x, lcm); + lcm = (lcm * x) / gcd; + } + lcm + } + + #[repr(u8)] + #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, Ord, PartialOrd)] + pub enum Dir { + N = b'U', + E = b'R', + S = b'D', + W = b'L', + } + + pub trait UnsoundUtilities<T> { + fn ψ(self) -> T; + } + + impl<T> UnsoundUtilities<T> for Option<T> { + fn ψ(self) -> T { + if cfg!(debug_assertions) && self.is_none() { + panic!(); + } + unsafe { self.unwrap_unchecked() } + } + } + + impl<T, E> UnsoundUtilities<T> for Result<T, E> { + #[cfg_attr(debug_assertions, track_caller)] + fn ψ(self) -> T { + if cfg!(debug_assertions) && self.is_err() { + panic!(); + } + unsafe { self.unwrap_unchecked() } + } + } + + pub struct LMap<K, V, F>(HashMap<K, V>, F) + where + F: Fn(K) -> Option<V>, + K: Eq + Hash + Copy; + impl<K: Eq + Hash + Copy, V, F> LMap<K, V, F> + where + F: Fn(K) -> Option<V>, + { + pub fn new(f: F) -> Self { + Self { + 0: HashMap::default(), + 1: f, + } + } + + pub fn get(&mut self, k: K) -> Option<&mut V> { + match self.0.entry(k) { + Entry::Occupied(x) => Some(x.into_mut()), + Entry::Vacant(e) => match self.1(k) { + Some(v) => Some(e.insert(v)), + None => None, + }, + } + } + } + + pub fn countg<N: Debug + PartialEq + Hash + Eq + Copy, I: Iterator<Item = N>>( + start: N, + graph: &mut impl Fn(N) -> I, + sum: &mut usize, + end: &mut impl Fn(N) -> bool, + has: &mut HashSet<N>, + ) { + if end(start) { + *sum += 1; + } else { + graph(start) + .map(|x| { + if has.insert(x) { + countg(x, graph, sum, end, has); + } + }) + .Θ(); + } + } + + // pub fn appearances(x: ) + + pub fn iterg<N: Debug + Copy, I: Iterator<Item = N>>( + start: N, + graph: &mut impl Fn(N) -> I, + end: &mut impl Fn(N) -> bool, + finally: &mut impl FnMut(N), + ) { + if end(start) { + finally(start); + } else { + graph(start).map(|x| iterg(x, graph, end, finally)).Θ(); + }; + } + + pub fn show<N: Debug + Eq + Hash + Copy + Ord, I: Iterator<Item = (N, u16)>, D: Display>( + graph: impl Fn(N) -> I, + start: N, + end: impl Fn(N) -> bool, + name: impl Fn(N) -> D, + ) { + println!("digraph {{"); + let mut s = HashSet::default(); + let mut q = BinaryHeap::new(); + q.push(Reverse((0, start))); + while let Some(Reverse((c, n))) = q.pop() { + if end(n) { + println!("}}"); + return; + } + if !s.insert(n) { + continue; + } + print!("\t{}", name(n)); + for (n, d) in graph(n) { + if s.contains(&n) { + continue; + } + print!(" -> {}", name(n)); + q.push(Reverse((c + d, n))); + } + println!(";"); + } + dang!(); + } + + pub fn dijkstra_h<N: Debug + Eq + Hash + Copy + Ord, I: Iterator<Item = (N, u16)>>( + graph: impl Fn(N) -> I, + start: N, + end: impl Fn(N) -> bool, + h: impl Fn(N) -> u16, + ) -> u16 { + let mut q = BinaryHeap::new(); + let mut s = HashSet::default(); + q.push(Reverse((h(start), 0, start))); + while let Some(Reverse((_, c, n))) = q.pop() { + if end(n) { + return c; + } + if !s.insert(n) { + continue; + } + for (n, d) in graph(n) { + if s.contains(&n) { + continue; + } + q.push(Reverse((h(n) + c + d, c + d, n))); + } + } + dang!() + } + + pub fn dijkstra<N: Debug + Eq + Hash + Copy + Ord, I: Iterator<Item = (N, u16)>>( + graph: impl Fn(N) -> I, + start: N, + end: impl Fn(N) -> bool, + ) -> u16 { + let mut q = BinaryHeap::new(); + let mut s = HashSet::default(); + q.push(Reverse((0, start))); + while let Some(Reverse((c, n))) = q.pop() { + if end(n) { + return c; + } + if !s.insert(n) { + continue; + } + for (n, d) in graph(n) { + if s.contains(&n) { + continue; + } + q.push(Reverse((c + d, n))); + } + } + dang!() + } + + impl std::ops::Add<(i64, i64)> for Dir { + type Output = (i64, i64); + fn add(self, (x, y): (i64, i64)) -> Self::Output { + match self { + Dir::N => (x, y - 1), + Dir::E => (x + 1, y), + Dir::S => (x, y + 1), + Dir::W => (x - 1, y), + } + } + } + + impl std::ops::Add<(i32, i32)> for Dir { + type Output = (i32, i32); + fn add(self, (x, y): (i32, i32)) -> Self::Output { + match self { + Dir::N => (x, y - 1), + Dir::E => (x + 1, y), + Dir::S => (x, y + 1), + Dir::W => (x - 1, y), + } + } + } + + impl std::ops::Add<(u16, u16)> for Dir { + type Output = (u16, u16); + + fn add(self, (x, y): (u16, u16)) -> Self::Output { + match self { + Dir::N => (x, y - 1), + Dir::E => (x + 1, y), + Dir::S => (x, y + 1), + Dir::W => (x - 1, y), + } + } + } + + impl std::ops::Add<(i16, i16)> for Dir { + type Output = (i16, i16); + fn add(self, (x, y): (i16, i16)) -> Self::Output { + match self { + Dir::N => (x, y - 1), + Dir::E => (x + 1, y), + Dir::S => (x, y + 1), + Dir::W => (x - 1, y), + } + } + } + + impl std::ops::Add<(u8, u8)> for Dir { + type Output = Option<(u8, u8)>; + + fn add(self, (x, y): (u8, u8)) -> Self::Output { + match self { + Dir::N => Some((x, y.checked_sub(1)?)), + Dir::E => Some((x + 1, y)), + Dir::S => Some((x, y + 1)), + Dir::W => Some((x.checked_sub(1)?, y)), + } + } + } + + pub fn pa<T: std::fmt::Debug>(a: &[T]) { + for e in a { + print!("{e:?}"); + } + println!(); + } + + pub fn gcd(mut a: u64, mut b: u64) -> u64 { + if a == 0 || b == 0 { + return a | b; + } + let shift = (a | b).trailing_zeros(); + a >>= shift; + loop { + b >>= b.trailing_zeros(); + if a > b { + swap(&mut a, &mut b); + } + b -= a; + if b == 0 { + break; + } + } + a << shift + } + + pub trait Λ { + fn λ<T: FromStr>(&self) -> T + where + <T as FromStr>::Err: std::fmt::Display; + } + + impl Λ for String { + fn λ<T: FromStr>(&self) -> T + where + <T as FromStr>::Err: std::fmt::Display, + { + self.as_str().λ() + } + } + impl Λ for &[u8] { + fn λ<T: FromStr>(&self) -> T + where + <T as FromStr>::Err: std::fmt::Display, + { + std::str::from_utf8(self).α().λ() + } + } + impl Λ for &str { + /// parse, unwrap + fn λ<T: FromStr>(&self) -> T + where + <T as FromStr>::Err: std::fmt::Display, + { + match self.parse() { + Ok(v) => v, + Err(e) => { + panic!( + "{e}: {self} should parse into {}", + std::any::type_name::<T>() + ) + } + } + } + } + pub trait Κ { + fn κ<T: FromStr>(self) -> impl Iterator<Item = T> + where + <T as FromStr>::Err: std::fmt::Display; + } + + impl Κ for &[u8] { + fn κ<T: FromStr>(self) -> impl Iterator<Item = T> + where + <T as FromStr>::Err: std::fmt::Display, + { + std::str::from_utf8(self).unwrap().κ() + } + } + + impl Κ for &str { + fn κ<T: FromStr>(self) -> impl Iterator<Item = T> + where + <T as FromStr>::Err: std::fmt::Display, + { + self.split_ascii_whitespace().map(|x| x.λ()) + } + } + + pub trait Α<T> { + fn α(self) -> T; + } + + impl<T, E: std::fmt::Display> Α<T> for Result<T, E> { + #[cfg_attr(debug_assertions, track_caller)] + fn α(self) -> T { + match self { + Ok(v) => v, + Err(e) => { + panic!("unwrap failed: {e}"); + } + } + } + } + impl<T> Α<T> for Option<T> { + #[cfg_attr(debug_assertions, track_caller)] + fn α(self) -> T { + match self { + Some(v) => v, + None => panic!("nothingness!"), + } + } + } + + pub trait Ͷ { + fn ͷ(self) -> impl Iterator<Item = u8>; + } + + macro_rules! digs { + ($for:ty) => { + impl Ͷ for $for { + fn ͷ(self) -> impl Iterator<Item = u8> { + let digits = (self.ilog10() + 1) as u8; + (0..digits) + .rev() + .map(move |n| ((self / (10 as $for).pow(n as _)) % 10) as u8) + } + } + }; + } + digs!(u64); + digs!(i64); + digs!(i32); + digs!(u32); + digs!(u16); + digs!(i16); + digs!(u8); + digs!(i8); + + #[derive(Copy, Clone, PartialEq, PartialOrd)] + pub struct Ronge { + pub begin: u16, + pub end: u16, + } + + impl Debug for Ronge { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + write!(f, "{}..{}", self.begin, self.end) + } + } + + impl Display for Ronge { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + write!(f, "{}..{}", self.begin, self.end) + } + } + + impl From<RangeInclusive<u16>> for Ronge { + fn from(value: RangeInclusive<u16>) -> Self { + Self { + begin: *value.start(), + end: *value.end(), + } + } + } + + impl PartialEq<RangeInclusive<u16>> for Ronge { + fn eq(&self, other: &RangeInclusive<u16>) -> bool { + self == &Self::from(other.clone()) + } + } + + impl Ronge { + pub fn sane(self) -> bool { + self.end >= self.begin + } + pub fn checked_len(self) -> Option<u16> { + self.sane().then(|| self.len()) + } + pub fn len(self) -> u16 { + self.end - self.begin + } + + /// push up + pub fn pushu(&mut self, to: u16) { + self.begin = self.begin.max(to); + } + + /// push down + pub fn pushd(&mut self, to: u16) { + self.end = self.end.min(to); + } + + pub fn intersect(self, with: Self) -> Self { + Self { + begin: self.begin.max(with.begin), + end: self.end.min(with.end), + } + } + + pub fn news(&self, begin: u16) -> Self { + Self { + begin, + end: self.end, + } + } + + pub fn newe(&self, end: u16) -> Self { + Self { + begin: self.begin, + end, + } + } + + pub fn shrink(&mut self, with: Ronge) { + self.pushu(with.begin); + self.pushd(with.end); + } + } + + impl IntoIterator for Ronge { + type Item = u16; + + type IntoIter = std::ops::Range<u16>; + + fn into_iter(self) -> Self::IntoIter { + self.begin..self.end + } + } + + pub trait Μ where + Self: Sized, + { + fn μ(self, d: char) -> (Self, Self); + fn μκ<T: FromStr>(self, d: char) -> impl Iterator<Item = (T, T)> + where + <T as FromStr>::Err: std::fmt::Display; + + fn μ1(self, d: char) -> Self { + self.μ(d).1 + } + + fn μ0(self, d: char) -> Self { + self.μ(d).0 + } + + fn between(self, a: char, b: char) -> Self { + self.μ1(a).μ0(b) + } + } + + impl Μ for &[u8] { + fn μ(self, d: char) -> (Self, Self) { + let i = self + .iter() + .position(|&x| x == d as u8) + .unwrap_or_else(|| shucks!("{} should split at {d} fine", self.p())); + (&self[..i], &self[i + 1..]) + } + + fn μκ<T: FromStr>(self, d: char) -> impl Iterator<Item = (T, T)> + where + <T as FromStr>::Err: std::fmt::Display, + { + let (α, β) = self.μ(d); + α.κ::<T>().zip(β.κ::<T>()) + } + } + + pub fn gt<A: std::cmp::PartialOrd<T>, T>(n: T) -> impl Fn(A) -> bool { + move |a| a > n + } + + pub fn lt<A: std::cmp::PartialOrd<T>, T>(n: T) -> impl Fn(A) -> bool { + move |a| a < n + } + + impl Μ for &str { + fn μ(self, d: char) -> (Self, Self) { + self.split_once(d) + .unwrap_or_else(|| shucks!("{self} should split at {d} fine")) + } + + fn μκ<T: FromStr>(self, d: char) -> impl Iterator<Item = (T, T)> + where + <T as FromStr>::Err: std::fmt::Display, + { + let (α, β) = self.μ(d); + α.κ::<T>().zip(β.κ::<T>()) + } + } + + pub trait IterͶ: Iterator { + fn ͷ(self) -> impl Iterator<Item = u8>; + } + + impl<I: Iterator<Item = u64>> IterͶ for I { + fn ͷ(self) -> impl Iterator<Item = u8> { + self.flat_map(Ͷ::ͷ) + } + } + + pub trait TupleIterTools3<T, U, V>: Iterator { + fn l(self) -> impl Iterator<Item = T>; + fn m(self) -> impl Iterator<Item = U>; + fn r(self) -> impl Iterator<Item = V>; + fn lm(self) -> impl Iterator<Item = (T, U)>; + fn lr(self) -> impl Iterator<Item = (T, V)>; + fn mr(self) -> impl Iterator<Item = (U, V)>; + } + + pub trait TupleIterTools2<T, U>: Iterator { + fn l(self) -> impl Iterator<Item = T>; + fn r(self) -> impl Iterator<Item = U>; + } + + pub trait TupleIterTools2R<T, U>: Iterator { + fn l(self) -> impl Iterator<Item = T>; + fn r(self) -> impl Iterator<Item = U>; + } + + pub fn l<R, T, U>(f: impl Fn(T) -> R) -> impl Fn((T, U)) -> R { + move |(x, _)| f(x) + } + pub fn r<R, T, U>(f: impl Fn(U) -> R) -> impl Fn((T, U)) -> R { + move |(_, x)| f(x) + } + + pub trait FilterBy3<T, U, V>: Iterator { + fn fl(self, f: impl Fn(T) -> bool) -> impl Iterator<Item = (T, U, V)>; + fn fm(self, f: impl Fn(U) -> bool) -> impl Iterator<Item = (T, U, V)>; + fn fr(self, f: impl Fn(V) -> bool) -> impl Iterator<Item = (T, U, V)>; + } + + impl<T: Copy, U: Copy, V: Copy, I: Iterator<Item = (T, U, V)>> FilterBy3<T, U, V> for I { + fn fl(self, f: impl Fn(T) -> bool) -> impl Iterator<Item = (T, U, V)> { + self.filter(move |(x, _, _)| f(*x)) + } + + fn fm(self, f: impl Fn(U) -> bool) -> impl Iterator<Item = (T, U, V)> { + self.filter(move |(_, x, _)| f(*x)) + } + fn fr(self, f: impl Fn(V) -> bool) -> impl Iterator<Item = (T, U, V)> { + self.filter(move |(_, _, x)| f(*x)) + } + } + pub trait FilterBy<T, U>: Iterator { + fn fl(self, f: impl Fn(T) -> bool) -> impl Iterator<Item = (T, U)>; + fn fr(self, f: impl Fn(U) -> bool) -> impl Iterator<Item = (T, U)>; + } + + impl<T: Copy, U: Copy, I: Iterator<Item = (T, U)>> FilterBy<T, U> for I { + fn fl(self, f: impl Fn(T) -> bool) -> impl Iterator<Item = (T, U)> { + self.filter(move |(x, _)| f(*x)) + } + + fn fr(self, f: impl Fn(U) -> bool) -> impl Iterator<Item = (T, U)> { + self.filter(move |(_, x)| f(*x)) + } + } + + pub trait NumTupleIterTools { + fn πολλαπλασιάζω_και_αθροίζω(&mut self) -> u64; + } + + impl<I: Iterator<Item = (u64, u64)>> NumTupleIterTools for I { + fn πολλαπλασιάζω_και_αθροίζω(&mut self) -> u64 { + self.map(|(a, b)| a * b).sum() + } + } + + impl<T, U, I: Iterator<Item = (T, U)>> TupleIterTools2<T, U> for I { + fn l(self) -> impl Iterator<Item = T> { + self.map(|(x, _)| x) + } + + fn r(self) -> impl Iterator<Item = U> { + self.map(|(_, x)| x) + } + } + + impl<'a, T: Copy + 'a, U: Copy + 'a, I: Iterator<Item = &'a (T, U)>> TupleIterTools2R<T, U> for I { + fn l(self) -> impl Iterator<Item = T> { + self.map(|&(x, _)| x) + } + fn r(self) -> impl Iterator<Item = U> { + self.map(|&(_, x)| x) + } + } + + impl<T, U, V, I: Iterator<Item = (T, U, V)>> TupleIterTools3<T, U, V> for I { + fn l(self) -> impl Iterator<Item = T> { + self.map(|(x, _, _)| x) + } + + fn m(self) -> impl Iterator<Item = U> { + self.map(|(_, x, _)| x) + } + + fn r(self) -> impl Iterator<Item = V> { + self.map(|(_, _, x)| x) + } + + fn lm(self) -> impl Iterator<Item = (T, U)> { + self.map(|(a, b, _)| (a, b)) + } + + fn lr(self) -> impl Iterator<Item = (T, V)> { + self.map(|(a, _, b)| (a, b)) + } + + fn mr(self) -> impl Iterator<Item = (U, V)> { + self.map(|(_, a, b)| (a, b)) + } + } + + pub trait GreekTools<T>: Iterator { + fn Δ(&mut self) -> T; + fn ι<N>(&mut self) -> impl Iterator<Item = (T, N)> + where + Self: Ι<T, N>; + fn ι1<N>(&mut self) -> impl Iterator<Item = (T, N)> + where + Self: Ι<T, N>; + fn ν<const N: usize>(&mut self, into: &mut [T; N]) -> usize; + fn Θ(&mut self); + } + + pub trait ParseIter { + fn κ<T: FromStr>(&mut self) -> impl Iterator<Item = T> + where + <T as FromStr>::Err: std::fmt::Display; + } + + impl<'x, I: Iterator<Item = &'x [u8]>> ParseIter for I { + fn κ<T: FromStr>(&mut self) -> impl Iterator<Item = T> + where + <T as FromStr>::Err: std::fmt::Display, + { + self.flat_map(|x| x.κ()) + } + } + + pub trait Ι<T, N>: Iterator { + fn ι(&mut self) -> impl Iterator<Item = (T, N)>; + fn ι1(&mut self) -> impl Iterator<Item = (T, N)>; + } + + macro_rules! ι { + ($t:ty) => { + impl<T, I: Iterator<Item = T>> Ι<T, $t> for I { + fn ι(&mut self) -> impl Iterator<Item = (T, $t)> { + self.zip(0..) + } + + fn ι1(&mut self) -> impl Iterator<Item = (T, $t)> { + self.zip(1..) + } + } + }; + } + ι!(u8); + ι!(u16); + ι!(u32); + ι!(u64); + ι!(usize); + + pub fn nail<const N: usize, T: Copy>(x: &[T]) -> [T; N] { + unsafe { (x.as_ptr() as *const [T; N]).read() } + } + + pub mod reading { + #[inline] + pub fn 八(n: u64) -> u64 { + // reinterpret as u64 ("92233721" => 92233721) + // let n = u64::from_le_bytes(s); + // combine 4 pairs of single digits: + // split pieces into odd and even + // 1_7_3_2_ (le repr) + // _2_3_2_9 + // then combine + // _21_37_23_92 (le repr, each byte as 2 digits) + let n = ((n & 0x0f000f000f000f00) >> 8) + ((n & 0x000f000f000f000f) * 10); + // combine 2 pairs of 2 digits: + // split again + // _21___23__ + // ___37___92 + // then combine + // __14|137__36|7 (le repr, pipes separating bytes) + let n = ((n & 0x00ff000000ff0000) >> 16) + ((n & 0x000000ff000000ff) * 100); + // combine pair of 4 digits + // split again + // __14|137____ (then moved to ______14|137, as u64:3721) + // ______36|07 (as u64: 9223) + // then combine + ((n & 0x0000ffff00000000) >> 32) + ((n & 0x000000000000ffff) * 10000) + } + + use std::{ + io::{self, Read}, + ops::{Add, BitOrAssign, Shl}, + }; + pub trait Ext { + fn rd<const N: usize>(&mut self) -> io::Result<[u8; N]>; + fn by(&mut self) -> io::Result<u8> { + Ok(self.rd::<1>()?[0]) + } + } + + impl<T: Read> Ext for T { + fn rd<const N: usize>(&mut self) -> io::Result<[u8; N]> { + let mut buf = [0; N]; + self.read_exact(&mut buf)?; + Ok(buf) + } + } + use crate::util::prelude::*; + pub fn κ(x: &[u8], v: &mut Vec<u64>) { + let mut s = 0; + for &b in x { + match b { + b' ' => { + v.push(s); + s = 0; + } + b => { + s = s * 10 + (b - b'0') as u64; + } + } + } + } + pub trait Ten { + fn ten() -> Self; + } + macro_rules! tenz { + ($for:ty) => { + impl Ten for $for { + fn ten() -> $for { + 10 + } + } + }; + } + tenz!(u8); + tenz!(u16); + tenz!(u32); + tenz!(u64); + tenz!(u128); + tenz!(i8); + tenz!(i16); + tenz!(i32); + tenz!(i64); + tenz!(i128); + + const DIG: [u8; 256] = [ + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 10, 11, 12, 13, 14, 15, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + ]; + + pub fn hex_dig(b: u8) -> u8 { + DIG[b.nat()] + // (b & 0xF) + 9 * (b >> 6) + } + + pub fn hexN< + T: From<u8> + TryFrom<usize> + Shl<T, Output = T> + BitOrAssign<T>, + const N: usize, + >( + a: [u8; N], + ) -> T { + let mut c = T::from(hex_dig(a[0])) << T::try_from((N - 1) * 4).ψ(); + for (&n, sh) in a[1..].iter().zip((0..N - 1).rev()) { + c |= T::from(hex_dig(n)) << T::try_from(sh * 4).ψ(); + } + c + } + + pub fn hex(mut d: &[u8]) -> Result<u32, ()> { + let &b = d.take_first().ok_or(())?; + let mut num = hex_dig(b) as u32; + while let Some(&b) = d.take_first() { + num = num * 16 + hex_dig(b) as u32; + } + Ok(num) + } + + pub fn 迄または完了< + T: Default + std::ops::Mul<T, Output = T> + Add<T, Output = T> + From<u8> + Copy + Ten, + >( + x: &mut &[u8], + until: u8, + ) -> T { + let mut n = T::default(); + while let Ok(x) = x.by() { + if x == until { + return n; + } + n = n * T::ten() + T::from(x - b'0') + } + n + } + + pub fn 負迄(x: &mut &[u8], until: u8) -> i64 { + let (sign, mut n) = match x.by().ψ() { + b'-' => (-1, 0), + b => (1, i64::from(b - b'0')), + }; + loop { + let byte = x.by().ψ(); + if byte == until { + return n * sign as i64; + } + n = n * 10 + i64::from(byte - b'0'); + } + } + + pub fn 迄< + T: Default + std::ops::Mul<T, Output = T> + Add<T, Output = T> + From<u8> + Copy + Ten, + >( + x: &mut &[u8], + until: u8, + ) -> T { + let mut n = T::default(); + loop { + let byte = x.by().ψ(); + if byte == until { + return n; + } + n = n * T::ten() + T::from(byte - b'0'); + } + } + + pub fn all< + T: Default + std::ops::Mul<T, Output = T> + Add<T, Output = T> + From<u8> + Copy + Ten, + >( + x: &[u8], + ) -> T { + let mut n = T::default(); + for &byte in x { + n = n * T::ten() + T::from(byte - b'0'); + } + n + } + } + + pub fn even(x: &usize) -> bool { + x % 2 == 0 + } + + impl<T, I: Iterator<Item = T>> GreekTools<T> for I { + #[cfg_attr(debug_assertions, track_caller)] + fn Δ(&mut self) -> T { + self.next().α() + } + + fn ν<const N: usize>(&mut self, into: &mut [T; N]) -> usize { + let mut set = 0; + for e in into { + let Some(y) = self.next() else { break }; + *e = y; + set += 1; + } + set + } + + fn ι<N>(&mut self) -> impl Iterator<Item = (T, N)> + where + Self: Ι<T, N>, + { + self.ι() + } + + fn ι1<N>(&mut self) -> impl Iterator<Item = (T, N)> + where + Self: Ι<T, N>, + { + self.ι1() + } + + fn Θ(&mut self) { + for _ in self {} + } + } + + pub trait TupleUtils<T, U> { + fn mr<W>(self, f: impl FnOnce(U) -> W) -> (T, W); + fn ml<V>(self, f: impl FnOnce(T) -> V) -> (V, U); + fn rev(self) -> (U, T); + } + + pub trait Widen<Wide> { + fn nat(self) -> usize; + fn widen(self) -> Wide; + } + + macro_rules! wide { + ($t:ty: $upper:ty) => { + impl Widen<$upper> for $t { + fn nat(self) -> usize { + self as _ + } + + fn widen(self) -> $upper { + self as _ + } + } + }; + } + wide!(u8: u16); + wide!(u16: u32); + wide!(u32: u64); + wide!(u64: u128); + + pub trait UnifiedTupleUtils<T> { + fn mb<U>(self, f: impl FnMut(T) -> U) -> (U, U); + } + + impl<T> UnifiedTupleUtils<T> for (T, T) { + fn mb<U>(self, mut f: impl FnMut(T) -> U) -> (U, U) { + (f(self.0), f(self.1)) + } + } + + impl<T, U> TupleUtils<T, U> for (T, U) { + fn mr<W>(self, f: impl FnOnce(U) -> W) -> (T, W) { + (self.0, f(self.1)) + } + fn ml<V>(self, f: impl FnOnce(T) -> V) -> (V, U) { + (f(self.0), self.1) + } + fn rev(self) -> (U, T) { + (self.1, self.0) + } + } + + #[allow(dead_code)] + fn cast_to<T: From<bool>>(x: bool, _to: T) -> T { + x.into() + } + + #[allow(unused_macros)] + macro_rules! bits { + ($bitset:ident + $bit:expr) => { + $bitset |= 1 << $bit + }; + ($holder:ident[$index:expr] + $bit:expr) => { + $holder[$index] |= 1 << $bit; + }; + ($bitset:ident[$bit:expr]) => { + ($bitset & 1 << $bit) != 0 + }; + ($holder:ident[$index:expr][$bit:expr]) => { + ($holder[$index] & 1 << $bit) != 0 + }; + ($holder:ident[$index:expr][$index2:expr][$bit:expr]) => { + ($holder[$index][$index2] & 1 << $bit) != 0 + }; + ($holder:ident[$index:expr][$index2:expr] + $bit:expr) => { + $holder[$index][$index2] |= 1 << $bit + }; + ($bitset:ident[$bit:expr] = $val:expr) => { + $bitset = ($bitset & !(1 << $bit)) | (crate::util::cast_to($val, $bitset) << $bit) + }; + ($bitset:ident - $bit:expr) => { + $bitset &= !(1 << $bit) + }; + ($bitset:ident ! $bit:expr) => { + $bitset ^= 1 << $bit + }; + } + pub(crate) use bits; + + pub struct Lines<'a> { + bytes: &'a [u8], + } + + impl<'a> Iterator for Lines<'a> { + type Item = &'a [u8]; + + fn next(&mut self) -> Option<Self::Item> { + self.bytes.take_line() + } + } + + impl<'a> std::iter::FusedIterator for Lines<'a> {} + + impl<'a> DoubleEndedIterator for Lines<'a> { + #[inline] + fn next_back(&mut self) -> Option<Self::Item> { + self.bytes.take_backline() + } + } + + pub trait IntoLines { + fn 行(&self) -> Lines<'_>; + } + + impl<T: AsRef<[u8]>> IntoLines for T { + fn 行(&self) -> Lines<'_> { + Lines { + bytes: self.as_ref(), + } + } + } + + pub trait Printable { + fn p(&self) -> impl std::fmt::Display; + } + + struct PrintU8s<'a>(&'a [u8]); + impl std::fmt::Display for PrintU8s<'_> { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + for &b in self.0 { + if b.is_ascii() { + f.write_char(b as char)?; + } else { + write!(f, "\\x{b:x}")?; + } + } + Ok(()) + } + } + + struct PrintManyU8s<'a, T: AsRef<[u8]>>(&'a [T]); + impl<T: AsRef<[u8]>> std::fmt::Display for PrintManyU8s<'_, T> { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + for row in self.0.as_ref() { + write!(f, "{},", row.as_ref().p())?; + } + Ok(()) + } + } + impl Printable for [Vec<u8>] { + fn p(&self) -> impl std::fmt::Display { + PrintManyU8s(self) + } + } + + impl Printable for [&&[u8]] { + fn p(&self) -> impl std::fmt::Display { + PrintManyU8s(self) + } + } + + impl Printable for [&[u8]] { + fn p(&self) -> impl std::fmt::Display { + PrintManyU8s(self) + } + } + + impl Printable for [u8] { + fn p(&self) -> impl std::fmt::Display { + PrintU8s(self) + } + } + + impl Printable for Vec<u8> { + fn p(&self) -> impl std::fmt::Display { + PrintU8s(self) + } + } + + pub fn sort<T: Ord>(mut x: Vec<T>) -> Vec<T> { + x.sort_unstable(); + x + } + + pub trait TakeLine<'b> { + fn take_line<'a>(&'a mut self) -> Option<&'b [u8]>; + fn take_backline<'a>(&'a mut self) -> Option<&'b [u8]>; + } + + impl<'b> TakeLine<'b> for &'b [u8] { + fn take_line<'a>(&'a mut self) -> Option<&'b [u8]> { + match memchr::memchr(b'\n', self) { + None if self.is_empty() => None, + None => Some(std::mem::replace(self, b"")), + Some(end) => { + let line = &self[..end]; + *self = &self[end + 1..]; + Some(line) + } + } + } + + fn take_backline<'a>(&'a mut self) -> Option<&'b [u8]> { + let end = self.len().checked_sub(1)?; + match memchr::memrchr(b'\n', &self[..end]) { + None => Some(std::mem::replace(self, b"")), + Some(end) => { + let line = &self[end + 1..]; + *self = &self[..end]; + Some(line) + } + } + } + } + + impl<'b> TakeLine<'b> for &'b str { + fn take_line<'a>(&'a mut self) -> Option<&'b [u8]> { + match memchr::memchr(b'\n', self.as_bytes()) { + None if self.is_empty() => None, + None => Some(std::mem::replace(self, "").as_bytes()), + Some(end) => { + let line = self[..end].as_bytes(); + *self = &self[end + 1..]; + Some(line) + } + } + } + + fn take_backline<'a>(&'a mut self) -> Option<&'b [u8]> { + let end = self.len().checked_sub(1)?; + match memchr::memrchr(b'\n', &self.as_bytes()[..end]) { + None => Some(std::mem::replace(self, "").as_bytes()), + Some(end) => { + let line = &self[end + 1..]; + *self = &self[..end]; + Some(line.as_bytes()) + } + } + } + } + + pub trait IntoCombinations<T: Copy>: Iterator { + /// LEAKY + fn combine(self) -> impl Iterator<Item = (T, T)>; + } + + impl<T: Copy + 'static, I: Iterator<Item = T>> IntoCombinations<T> for I { + fn combine(self) -> impl Iterator<Item = (T, T)> { + let x = Box::leak(self.collect::<Box<[_]>>()); + x.iter() + .enumerate() + .flat_map(|(i, &a)| x[i..].iter().map(move |&b| (a, b))) + } + } + + pub trait Skip { + fn skip(&mut self, n: usize); + } + + impl<T> Skip for &[T] { + #[cfg_attr(debug_assertions, track_caller)] + fn skip(&mut self, n: usize) { + if cfg!(debug_assertions) { + *self = &self[n..]; + } else { + *self = C! { &self[n..] }; + } + } + } + + impl Skip for &str { + #[cfg_attr(debug_assertions, track_caller)] + fn skip(&mut self, n: usize) { + if cfg!(debug_assertions) { + *self = &self[n..]; + } else { + *self = C! { &self[n..] }; + } + } + } + + /// WYRAND based rng's + pub mod rand { + /// WYRAND + pub fn u64() -> u64 { + static mut STATE: u64 = 0; + let tmp = unsafe { + STATE = STATE.wrapping_add(0x60bee2bee120fc15); + (STATE as u128).wrapping_mul(0xa3b195354a39b70d) + }; + let m1 = (tmp >> 64) ^ tmp; + let tmp = m1.wrapping_mul(0x1b03738712fad5c9); + ((tmp >> 64) ^ tmp) as u64 + } + + /// 0..N + pub mod limit { + use super::super::Widen; + + pub fn u64(of: u64) -> u64 { + ((super::u64().widen().wrapping_mul(of.widen())) >> 64) as u64 + } + } + + pub fn u32() -> u32 { + u64() as u32 + } + + pub fn u16() -> u16 { + u64() as u16 + } + + pub fn f32() -> f32 { + (1.0 / ((1u32 << 24) as f32)) * ((u32() >> 8) as f32) + } + + pub fn f64() -> f64 { + (1.0 / ((1u64 << 53) as f64)) * ((u64() >> 11) as f64) + } + } +} + +pub use util::prelude::*; + +pub fn run(i: &str) -> impl Display { + let re = regex::Regex::new(r"mul\(([0-9]+),([0-9]+)\)|don't\(\)|do\(\)").unwrap(); + let mut on = true; + re.captures_iter(i) + .map(|find| unsafe { + match find.get(0).unwrap_unchecked().as_str() { + "don't()" => on = false, + "do()" => on = true, + _ if on => { + return reading::all::<u32>(find.get(1).ψ().as_str().as_bytes()) + * reading::all::<u32>(find.get(2).ψ().as_str().as_bytes()) + } + _ => (), + }; + 0 + }) + .sum::<u32>() + + // i.行() + // .filter(|x| { + // // let x = x.κ::<u64>().collect_vec(); + // }) + // .count() +} diff --git a/src/inp.txt b/src/inp.txt index cd46e29..b004787 100644 --- a/src/inp.txt +++ b/src/inp.txt @@ -1,1000 +1,6 @@ -16 19 21 24 21 -15 18 19 22 24 25 25 -80 81 83 84 87 89 93 -6 7 8 9 10 13 18 -60 62 61 64 66 67 -76 79 81 84 82 80 -70 73 72 74 74 -67 68 71 74 73 77 -56 57 60 59 61 64 67 74 -37 38 39 40 40 43 -90 92 95 95 96 97 94 -80 83 86 86 86 -44 47 49 49 51 54 58 -69 71 74 74 81 -66 68 72 75 77 -34 35 39 41 38 -58 60 63 67 70 72 72 -43 46 47 51 52 53 56 60 -35 36 37 41 44 50 -63 64 67 69 71 72 78 80 -19 22 23 30 28 -20 21 24 30 30 -75 78 80 83 90 91 95 -16 17 20 22 23 29 31 36 -22 21 24 26 28 -87 84 87 88 86 -48 46 48 51 51 -40 37 40 43 44 48 -77 75 78 79 81 84 86 91 -43 41 40 42 44 -32 30 31 32 35 32 29 -87 84 81 83 83 -43 41 44 47 48 45 49 -49 48 51 53 54 57 54 61 -68 66 69 69 72 75 77 -9 7 8 10 10 12 11 -77 74 77 77 77 -5 2 4 4 8 -34 33 36 36 42 -11 9 13 15 18 21 -22 21 22 23 27 24 -68 67 70 74 77 80 82 82 -87 86 87 91 95 -26 23 27 28 30 35 -23 20 21 28 31 -85 83 89 92 95 96 94 -32 31 38 40 40 -40 38 40 41 43 49 51 55 -22 19 21 23 29 35 -86 86 89 91 94 96 98 -72 72 73 75 77 78 76 -42 42 45 48 49 49 -41 41 43 46 48 49 53 -35 35 37 39 41 43 48 -85 85 86 83 86 87 88 91 -20 20 19 20 21 20 -13 13 14 13 15 18 18 -48 48 50 48 50 54 -26 26 23 25 30 -62 62 64 66 66 67 -31 31 32 34 35 35 38 37 -11 11 14 14 14 -6 6 9 12 12 13 14 18 -5 5 5 7 9 14 -87 87 91 92 95 96 99 -61 61 65 67 64 -77 77 78 82 85 85 -48 48 52 53 57 -69 69 70 74 81 -29 29 30 32 35 37 44 46 -52 52 54 56 57 63 64 62 -42 42 45 47 48 51 57 57 -57 57 60 65 69 -28 28 33 34 36 38 44 -41 45 48 50 52 55 58 -79 83 84 85 86 83 -69 73 74 77 79 81 81 -14 18 21 22 24 28 -26 30 33 36 43 -8 12 13 12 14 16 17 -84 88 91 92 89 92 94 92 -30 34 32 34 37 37 -3 7 5 6 9 10 14 -31 35 37 35 36 39 45 -59 63 65 66 67 67 68 -13 17 18 21 21 18 -72 76 78 79 82 82 82 -4 8 9 9 10 13 14 18 -42 46 49 49 52 57 -17 21 24 28 29 -64 68 69 73 75 78 77 -57 61 63 67 67 -11 15 19 22 26 -78 82 83 87 94 -34 38 45 47 48 49 52 -44 48 55 56 55 -45 49 52 57 59 60 63 63 -48 52 55 62 66 -14 18 20 27 34 -9 15 18 20 23 25 -4 10 11 12 14 17 18 16 -4 10 12 13 15 17 17 -18 23 24 25 27 31 -27 33 35 37 40 42 47 -16 22 24 21 22 25 27 -42 49 52 49 47 -39 44 45 43 44 46 49 49 -29 36 39 42 45 46 43 47 -37 42 43 42 45 48 53 -54 60 63 63 65 -66 71 73 76 76 79 77 -56 62 62 64 66 66 -69 76 79 82 83 83 87 -77 84 84 87 93 -76 81 85 87 89 91 94 -70 77 81 82 85 87 89 87 -14 20 22 26 28 28 -56 61 65 68 72 -78 85 86 90 95 -22 29 30 36 39 40 42 44 -18 25 27 28 35 38 39 38 -15 21 24 25 27 34 34 -21 26 27 33 36 40 -42 48 49 51 52 57 64 -97 96 94 91 88 89 -74 71 68 67 66 66 -67 64 61 58 57 53 -63 61 60 57 54 52 51 44 -41 40 37 35 34 35 33 -53 50 52 51 52 -31 28 25 24 23 20 22 22 -25 24 27 25 24 21 18 14 -82 80 78 81 78 76 70 -36 33 32 31 31 30 -66 65 65 64 63 61 59 61 -82 79 79 76 75 72 72 -94 92 90 90 87 85 81 -22 19 19 18 13 -39 38 35 34 31 29 25 24 -72 70 67 63 62 59 58 59 -28 26 23 19 19 -24 22 20 16 13 10 9 5 -63 62 58 57 52 -27 25 23 21 16 14 13 11 -76 74 72 65 64 65 -25 23 17 14 14 -78 77 76 69 68 67 64 60 -78 76 70 68 66 65 63 58 -63 66 64 63 62 61 60 57 -61 63 60 57 54 53 56 -90 92 89 88 85 83 82 82 -41 42 39 38 36 35 33 29 -15 17 15 12 11 9 3 -77 79 78 77 80 79 76 -43 46 44 45 44 41 42 -27 30 33 32 32 -18 19 16 13 16 12 -16 17 14 12 10 8 11 6 -77 80 80 78 75 -31 34 34 32 34 -3 6 5 5 2 2 -76 78 75 72 69 69 65 -43 45 43 43 41 35 -36 39 38 35 33 29 28 -81 84 81 77 75 78 -40 42 38 36 33 32 29 29 -29 31 29 28 25 24 20 16 -80 82 79 76 75 71 69 63 -49 52 50 47 46 41 39 -78 79 78 77 72 69 66 67 -12 13 11 5 5 -12 15 14 9 8 7 6 2 -44 46 45 43 38 36 30 -61 61 58 56 53 52 50 47 -35 35 32 31 28 30 -46 46 44 42 42 -80 80 77 76 72 -63 63 60 59 56 55 49 -77 77 80 78 75 73 -52 52 51 52 53 -12 12 11 9 10 10 -60 60 63 61 58 54 -67 67 69 67 62 -95 95 93 93 92 91 -53 53 52 52 51 48 51 -67 67 67 66 63 63 -11 11 10 7 7 3 -26 26 23 21 20 20 13 -80 80 78 74 73 72 70 67 -54 54 53 49 52 -63 63 62 59 55 53 53 -61 61 57 55 51 -69 69 68 66 62 55 -85 85 82 75 74 73 72 -47 47 42 40 39 37 34 36 -60 60 59 58 55 52 47 47 -77 77 75 69 68 64 -53 53 52 45 44 43 36 -43 39 36 33 30 29 26 23 -65 61 60 57 54 56 -55 51 48 47 45 42 42 -52 48 47 45 43 41 37 -29 25 24 23 22 17 -38 34 37 35 32 29 28 26 -24 20 19 17 15 14 17 20 -33 29 28 25 26 26 -38 34 35 32 31 27 -33 29 27 24 23 24 23 17 -36 32 32 31 29 26 -13 9 8 5 3 1 1 4 -6 2 1 1 1 -78 74 73 72 72 70 69 65 -44 40 40 37 30 -41 37 33 30 28 -88 84 83 79 78 75 73 74 -12 8 4 2 1 1 -65 61 57 54 50 -85 81 77 74 68 -76 72 66 64 62 -97 93 90 87 81 84 -64 60 53 51 48 48 -56 52 50 45 43 39 -56 52 49 43 40 39 36 30 -60 53 51 50 48 -36 31 29 26 25 24 26 -55 50 48 47 44 42 41 41 -90 85 83 81 77 -89 82 80 77 70 -56 49 52 49 47 -9 3 5 3 6 -9 4 5 4 4 -18 12 14 12 8 -66 59 58 56 53 54 49 -97 90 88 87 84 82 82 80 -60 55 53 52 52 54 -12 5 5 4 4 -26 19 19 16 15 11 -68 62 60 57 56 56 54 47 -59 52 48 46 45 42 -21 16 12 9 12 -99 92 91 88 84 81 81 -58 52 49 45 43 42 38 -48 41 38 36 35 34 30 23 -31 26 24 18 15 13 -18 13 11 6 8 -99 93 88 85 84 84 -85 78 75 73 68 64 -86 81 75 72 66 -5 9 7 9 6 -22 26 29 32 29 31 34 34 -22 29 30 32 34 39 45 -52 45 43 41 40 37 32 34 -30 32 34 39 43 -11 16 18 22 22 -68 72 75 76 79 82 86 85 -69 74 76 80 84 -65 65 63 61 57 55 53 48 -26 25 20 17 15 12 9 -27 29 28 23 21 16 -49 53 54 57 59 62 66 -72 72 73 80 82 85 -44 47 49 50 54 55 57 57 -20 19 17 19 21 -18 18 22 24 26 29 31 32 -48 52 54 54 56 56 -72 76 79 78 84 -64 60 57 53 48 -48 44 42 40 37 33 32 35 -52 52 48 45 44 41 38 40 -70 76 78 80 80 87 -55 54 52 48 44 -39 38 32 31 30 28 22 -8 8 5 1 1 -43 48 50 53 57 -29 32 29 27 28 26 27 -44 49 51 53 60 61 65 -16 17 10 8 8 -36 31 28 25 22 20 20 17 -61 54 51 44 42 39 35 -96 90 88 84 83 80 79 -55 58 57 53 50 50 -41 46 48 50 48 54 -7 11 12 14 14 17 23 -79 82 81 77 74 77 -34 28 24 21 22 -77 81 84 86 87 90 94 94 -67 74 77 79 80 83 87 90 -94 90 89 84 80 -65 64 63 60 60 -40 44 47 48 52 53 55 -35 35 34 33 32 29 27 29 -75 82 85 88 90 89 88 -92 88 88 87 86 83 80 -99 92 91 86 84 -11 9 6 2 5 -57 57 50 48 44 -21 18 19 23 28 -30 33 31 31 30 27 23 -22 22 22 19 14 -61 57 54 54 52 45 -81 81 84 82 80 -93 93 90 88 91 90 87 83 -29 36 40 41 47 -84 83 84 86 86 88 -33 37 38 45 52 -56 60 64 65 66 67 71 -98 98 97 96 96 94 94 -96 89 86 84 77 74 68 -51 45 44 43 36 36 -66 63 70 73 79 -84 79 76 74 71 71 70 70 -27 23 22 19 14 13 10 5 -91 84 83 82 80 76 -13 14 17 20 21 26 26 -96 97 96 93 89 88 86 -39 45 46 43 44 45 -87 80 76 75 72 72 -86 88 89 90 92 93 92 91 -45 45 48 50 57 54 -65 63 65 67 70 67 -38 34 32 32 30 27 25 21 -17 21 23 20 22 23 26 28 -65 66 71 74 75 -6 6 9 12 15 18 22 -76 78 76 78 80 81 88 -32 25 24 22 21 21 -49 50 52 54 54 56 59 59 -16 13 16 19 20 27 29 -71 71 73 71 70 -75 69 66 66 65 58 -58 55 57 60 61 64 66 73 -52 53 53 51 48 47 44 -28 21 19 17 15 11 7 -57 60 61 64 61 63 65 69 -8 5 8 9 10 14 -65 58 56 56 53 51 54 -68 67 69 76 80 -21 21 21 18 17 14 12 8 -67 66 68 66 63 60 54 -26 27 25 20 19 17 14 16 -31 30 33 34 34 -53 55 59 62 60 -96 92 95 93 90 89 83 -13 18 20 23 26 25 29 -36 36 36 35 36 -61 61 58 56 52 49 46 -38 35 38 41 38 40 39 -11 14 13 10 8 2 -11 14 15 21 18 -50 53 53 51 48 47 47 -27 25 23 25 23 26 -48 48 45 44 45 42 45 -66 62 61 59 54 51 53 -6 6 8 5 7 8 9 14 -67 67 65 68 69 72 72 -66 64 65 66 73 70 -94 92 94 95 97 99 -90 89 86 85 84 82 82 78 -77 77 81 84 87 87 -31 36 38 36 39 41 42 42 -73 69 68 67 68 66 66 -14 12 11 10 7 4 6 6 -29 25 23 22 19 17 16 10 -80 81 80 78 79 79 -9 7 7 9 10 7 -88 84 81 79 79 79 -27 28 29 32 33 35 38 42 -13 11 8 8 6 5 8 -30 37 44 47 48 -53 54 61 62 65 68 74 -54 54 51 44 41 38 35 35 -38 38 35 30 28 25 28 -83 90 93 96 94 -70 74 75 77 80 81 82 -71 74 71 70 68 67 68 -35 35 33 36 39 41 45 -32 29 27 23 23 -45 49 51 53 56 61 61 -20 20 18 19 13 -64 60 58 55 52 -2 2 2 5 6 10 -68 69 67 65 63 63 -67 71 74 76 79 79 -42 37 34 32 31 29 28 26 -24 28 31 35 37 40 42 49 -79 77 80 80 80 -58 51 50 50 47 46 42 -23 28 35 37 40 43 43 -26 30 31 33 32 35 39 -53 55 58 58 62 -88 82 80 78 75 77 75 -70 68 69 70 70 72 79 -27 29 31 31 34 36 38 39 -3 4 5 6 7 9 9 15 -46 45 41 38 37 31 -51 52 52 55 56 59 56 -69 68 69 73 73 -78 84 86 86 88 89 93 -14 7 9 8 6 3 6 -28 26 24 22 19 16 15 11 -86 86 81 78 75 74 -50 43 39 37 35 30 -54 60 64 65 66 63 -54 54 51 48 45 -74 74 74 77 80 81 82 81 -21 21 18 14 11 9 5 -49 54 55 57 57 -79 78 77 75 74 71 70 64 -15 15 18 20 22 -98 91 90 89 87 86 89 83 -95 91 90 86 83 -69 67 71 73 76 80 -57 57 55 52 52 -74 74 75 78 82 79 -47 43 45 43 41 40 38 39 -70 74 76 78 79 79 83 -88 88 90 93 94 93 -83 83 85 86 86 -55 56 57 58 62 64 67 68 -86 86 91 94 94 -75 76 77 74 77 80 83 86 -51 58 58 61 64 67 68 68 -67 63 62 61 59 56 54 50 -97 91 89 88 87 86 79 -54 47 45 48 47 44 42 38 -22 19 22 19 20 22 26 -29 26 24 23 20 13 11 11 -3 3 4 6 10 16 -52 56 57 62 66 -94 96 96 93 88 -70 70 70 73 76 79 79 -36 35 38 37 36 33 31 -31 31 32 35 36 41 -17 14 12 11 8 6 9 5 -96 92 91 84 81 81 -76 72 68 66 65 65 -1 4 6 7 11 12 16 -57 52 51 50 52 51 51 -1 5 6 7 9 12 15 14 -66 66 69 68 70 -47 43 42 35 33 -59 57 59 64 65 67 67 -19 19 19 21 24 26 28 -51 51 49 47 40 -52 50 47 47 47 -92 89 89 86 81 -34 30 33 32 29 25 -6 10 13 14 15 20 -51 47 46 44 40 37 36 32 -62 58 58 56 53 50 52 -26 26 24 23 20 19 15 -36 34 33 32 25 24 23 26 -53 54 55 56 56 -29 29 30 27 25 25 -70 75 77 79 85 -18 18 16 16 13 10 -80 85 87 90 91 94 -56 59 56 56 54 52 55 -22 18 20 18 17 16 -12 10 11 14 18 20 21 22 -94 96 93 86 85 83 -54 56 54 52 51 53 51 49 -72 75 71 69 66 64 58 -41 45 46 47 54 56 59 -71 71 75 77 81 -14 17 16 13 15 11 -4 4 9 10 12 16 -71 72 73 76 79 76 -67 69 66 67 65 58 -32 34 31 30 29 28 25 23 -38 35 35 33 30 -48 49 52 55 58 59 62 67 -45 51 52 52 54 -28 34 36 38 38 36 -12 15 11 9 5 -36 33 36 37 41 43 46 43 -91 90 86 83 80 77 -48 55 61 63 64 66 65 -55 55 56 56 62 -64 64 59 58 57 56 50 -16 13 11 10 7 5 8 -26 26 31 32 34 41 -58 57 50 48 46 42 -23 19 18 16 17 -15 18 21 24 27 29 32 -63 60 57 55 54 52 51 -84 82 80 77 76 75 -40 42 44 46 48 51 53 -91 89 86 84 81 -37 40 41 42 45 46 49 52 -90 87 85 84 83 81 78 76 -9 10 11 13 14 16 -35 34 31 28 26 24 22 21 -96 95 93 90 87 86 -45 46 49 52 53 55 57 -54 56 58 61 62 -44 47 48 50 53 -79 81 82 83 86 87 -15 17 18 19 22 25 26 27 -26 29 30 33 35 -90 89 87 86 85 83 80 -79 80 82 83 84 -42 45 47 49 50 -89 88 87 86 83 82 80 -22 23 24 26 28 -51 48 46 43 40 37 36 -1 3 5 7 8 10 12 -87 84 83 81 80 78 77 76 -76 74 71 69 66 63 61 -20 21 23 26 29 31 33 34 -48 47 45 42 41 40 39 -56 53 52 51 48 45 42 39 -31 32 34 36 39 41 -40 37 35 33 30 27 25 22 -76 74 73 70 68 66 -67 64 62 60 59 -35 34 31 28 25 22 -93 91 90 88 85 83 81 -7 10 11 14 16 17 20 -37 35 34 31 28 -58 59 60 63 64 66 68 -13 12 11 9 7 5 4 1 -80 77 74 73 71 68 65 63 -93 91 89 88 87 84 81 79 -87 84 81 78 77 75 -70 72 75 78 80 82 83 86 -69 67 65 63 60 59 56 53 -23 20 17 16 15 -64 65 68 70 71 72 -79 80 81 84 86 -15 18 21 23 25 27 -39 36 35 33 30 27 24 22 -54 53 51 50 47 -68 67 65 63 61 59 -99 97 95 93 92 91 88 -71 68 65 63 61 59 -66 64 63 60 58 57 -51 53 56 58 61 63 -84 87 89 91 92 95 -30 31 34 37 38 39 -57 58 59 61 63 66 -62 64 65 68 70 71 72 73 -23 21 20 17 15 14 12 11 -53 56 58 60 62 63 64 -76 74 72 70 68 66 64 61 -88 85 84 83 80 78 -41 38 37 34 33 31 29 -33 35 37 39 42 45 -34 32 29 26 24 -95 93 90 87 84 82 79 78 -21 24 25 28 31 -83 86 88 91 94 96 98 -83 81 79 78 77 74 71 69 -84 83 80 79 76 75 74 -35 32 31 28 26 23 22 20 -48 46 44 41 38 37 -89 91 93 94 97 99 -14 16 17 18 20 -23 22 19 16 13 10 -78 80 81 82 84 85 88 -25 23 22 21 20 -33 32 29 28 26 24 21 19 -80 78 76 73 72 69 -82 81 79 78 76 73 -54 51 48 45 44 -34 32 29 27 24 21 19 16 -70 69 66 63 61 58 55 52 -29 26 24 21 18 15 13 12 -81 84 86 87 88 91 93 94 -85 82 79 76 73 70 68 67 -82 81 80 77 76 75 72 -42 39 38 36 35 -71 74 77 80 81 83 -32 35 36 37 40 -59 57 54 53 52 -36 33 31 30 27 25 23 -89 86 83 81 79 76 74 73 -76 77 80 83 86 88 -72 70 69 66 65 -27 25 24 21 19 16 -57 60 63 66 69 70 73 75 -34 35 36 38 40 43 46 -26 28 29 32 35 37 38 41 -14 12 9 7 5 -11 14 17 18 21 24 -47 45 42 39 36 33 -52 55 58 59 60 63 -83 81 80 78 76 74 71 70 -10 11 13 15 16 17 20 22 -67 66 63 61 58 55 -83 86 89 91 93 -78 81 84 87 89 -51 49 46 45 42 40 38 -69 66 63 62 61 60 58 -69 70 72 75 78 80 83 -26 29 30 33 34 35 -48 45 43 41 38 -76 73 70 69 67 66 -67 70 73 76 78 81 -48 46 43 41 38 36 -77 75 73 70 69 -4 6 9 10 12 14 17 20 -21 23 24 27 29 30 31 -77 75 74 73 70 69 66 -18 17 16 14 12 -46 44 41 39 38 -29 26 25 24 21 19 -5 7 9 10 11 12 14 15 -67 64 63 60 57 55 54 -26 29 30 31 33 36 38 -27 29 30 32 35 -27 25 23 22 20 19 16 14 -51 53 55 58 59 60 -22 19 17 16 15 12 11 -29 26 23 22 19 16 14 12 -5 7 9 10 13 -51 52 55 56 57 58 59 -46 49 50 53 54 57 58 -48 47 46 45 43 42 40 37 -57 59 61 63 66 69 -60 58 55 53 51 48 47 -89 88 86 85 82 80 79 -47 45 42 41 38 36 34 -93 92 89 86 85 83 -46 49 52 54 55 57 58 60 -47 49 51 54 57 58 61 62 -35 38 41 42 45 48 49 -45 47 49 52 55 58 -60 57 55 52 51 49 47 44 -62 61 58 56 55 53 50 47 -49 47 44 43 40 39 38 37 -56 53 50 49 48 46 44 41 -42 41 39 37 34 33 -57 55 52 50 47 45 -86 83 81 78 75 73 70 -13 12 9 8 7 4 -4 5 6 8 11 13 16 -25 23 22 19 17 16 14 -85 88 89 90 91 92 93 96 -89 88 85 84 81 79 78 -37 39 42 43 46 49 50 -78 76 73 71 68 67 66 -44 45 48 49 51 54 57 -61 60 58 56 55 54 52 50 -13 16 19 20 23 24 -50 47 44 43 41 -21 23 24 27 28 31 34 -22 25 28 31 32 -25 26 29 31 33 35 -87 89 91 93 95 98 -16 17 20 21 23 24 -71 72 75 78 80 81 -79 82 84 85 88 -69 66 63 60 59 57 54 53 -42 40 39 37 34 33 30 -62 64 67 68 70 71 74 -22 24 27 30 33 34 35 -13 11 10 8 7 5 -98 97 94 92 91 90 -24 27 30 32 34 36 38 40 -7 10 11 12 14 15 18 -75 76 79 80 83 86 89 90 -17 14 12 11 8 7 -60 61 62 64 65 66 68 -67 68 71 72 74 -50 53 54 55 56 58 -68 65 64 61 60 58 55 54 -85 84 83 82 79 -54 57 58 60 61 -70 71 74 76 78 81 84 86 -28 27 26 23 22 21 -88 90 91 93 96 99 -39 38 37 36 33 31 30 -41 43 44 46 47 -70 68 65 63 60 59 58 55 -61 60 59 57 55 53 52 49 -54 52 51 50 47 45 44 -11 14 15 18 19 20 21 -76 73 70 68 65 64 61 -45 46 49 52 53 54 -51 50 47 44 41 -27 29 30 33 36 38 39 -27 25 22 21 20 -56 57 58 60 63 65 66 67 -8 6 5 3 1 -51 49 46 45 42 39 38 36 -75 73 71 68 65 -77 78 81 82 83 -74 72 69 68 65 63 61 -19 21 24 25 27 -24 26 28 29 32 33 36 39 -57 56 55 52 49 -63 62 59 57 56 53 -44 47 49 51 53 54 55 -26 25 22 19 16 -78 76 73 71 68 66 -74 72 69 68 66 63 60 -32 33 35 36 37 39 40 41 -24 26 28 29 32 35 -65 63 62 61 60 59 56 54 -53 50 48 47 46 43 -61 58 56 55 53 52 51 49 -48 46 45 43 40 38 -15 12 11 8 6 5 4 -31 28 26 23 22 -54 55 56 58 60 62 63 66 -65 67 69 72 74 76 -46 49 52 54 56 -35 34 32 29 26 -12 11 9 6 4 -19 18 16 13 10 9 -35 32 31 30 29 -51 53 55 56 58 60 62 -23 20 19 16 14 11 -14 17 18 19 21 23 -3 4 7 9 10 13 -37 35 32 31 28 26 24 22 -17 20 21 23 24 27 -37 40 42 44 47 48 51 52 -77 76 73 71 70 69 66 -91 90 88 87 86 85 82 80 -71 68 65 62 59 58 57 -6 8 10 11 13 16 17 -28 29 31 34 37 39 41 44 -2 5 8 9 10 13 15 -67 65 63 62 59 56 53 51 -5 6 9 10 13 16 19 21 -84 86 87 90 91 93 95 97 -46 47 49 52 54 -74 72 71 70 69 -8 9 11 14 17 19 20 23 -28 25 22 19 18 16 15 -29 30 32 33 34 36 37 40 -73 74 75 77 79 82 -37 36 35 34 32 30 27 -15 16 17 18 20 -71 70 69 66 65 63 61 -26 24 21 18 15 -66 69 72 75 78 -94 91 90 89 87 86 -46 48 49 51 52 55 58 -27 24 22 19 17 16 13 -65 66 68 71 73 76 79 -59 58 56 54 53 51 -35 36 39 40 41 43 45 -22 25 27 29 31 34 36 39 -33 35 36 37 38 -88 87 86 84 81 79 -43 40 38 35 32 30 27 -34 36 39 40 43 45 47 -27 26 24 23 21 18 15 14 -56 55 54 52 49 48 45 43 -26 27 30 33 36 39 -87 90 92 93 94 97 98 99 -67 66 63 62 60 58 55 -86 84 81 80 77 75 73 -64 61 58 57 55 -64 65 67 70 72 73 -86 89 92 94 96 99 -50 47 46 44 42 39 37 36 -77 80 82 85 87 89 -69 66 65 63 60 -33 36 37 39 41 43 45 46 -73 74 75 78 81 82 -52 49 48 45 42 41 38 35 -23 20 19 18 17 -34 36 37 38 41 44 -52 54 56 57 60 62 64 67 -15 18 19 20 23 25 -13 12 11 8 6 3 -15 16 18 21 24 26 27 -64 66 69 72 73 76 79 80 -40 41 43 45 46 48 50 52 -24 26 29 31 33 34 36 -52 50 48 46 44 41 40 37 -24 21 18 15 12 11 -77 80 81 82 84 85 87 88 -59 56 55 54 53 -51 50 47 45 42 40 -66 69 70 73 75 77 79 80 -43 46 49 50 51 -62 64 67 69 71 73 75 -66 68 71 74 76 78 79 80 -14 12 9 7 4 -26 29 31 33 36 39 -70 71 74 76 77 -82 83 86 89 91 93 95 -55 52 51 49 48 -18 17 16 13 11 -26 28 29 32 35 36 39 -34 37 38 41 43 44 47 48 -61 64 65 68 69 71 73 -84 86 88 90 93 -52 55 56 59 61 64 65 68 -16 18 21 23 26 28 30 32 -9 12 13 16 18 -20 21 23 26 28 29 30 33 -89 88 85 84 83 80 78 76 -71 70 67 65 62 -36 34 32 29 27 25 -86 84 82 81 78 77 -36 39 40 43 45 47 48 -80 77 76 73 72 71 -24 21 20 19 17 14 12 9 -39 37 35 34 33 30 27 -44 47 50 51 53 56 58 61 -66 64 62 59 58 56 53 50 -62 60 58 56 55 52 -67 69 72 75 77 -62 64 66 67 68 69 70 73 -41 43 45 48 51 -40 42 43 45 47 -33 35 37 38 40 41 -17 18 20 23 24 25 28 30 -16 17 19 21 23 -57 59 61 64 66 68 69 72 -99 96 94 93 90 -76 77 80 81 82 83 85 -21 19 17 15 12 11 -65 68 71 73 76 79 -7 10 11 14 17 20 21 -80 79 76 73 70 -76 79 81 83 84 87 89 -82 81 79 76 75 -50 47 45 44 43 42 40 -97 95 93 91 89 86 83 -88 89 91 93 95 96 -13 11 9 7 6 3 2 -74 76 79 82 85 87 90 93 -93 90 88 87 85 -51 49 46 44 43 40 39 -6 7 10 13 16 17 20 -77 75 73 70 69 66 64 63 -30 33 34 35 38 -49 51 52 54 56 -22 24 25 28 30 -18 19 22 24 27 30 33 35 -83 84 87 89 92 -32 35 36 37 40 43 -18 17 16 14 13 10 9 -53 51 49 46 45 42 -64 65 68 70 72 -72 69 68 65 64 -55 53 50 49 46 43 42 39 -53 52 50 48 45 42 39 -71 73 75 78 81 -83 85 86 89 91 94 -84 85 87 89 92 93 -27 24 23 22 19 18 -19 22 24 26 27 -58 57 56 55 52 49 47 -80 79 76 75 74 -89 86 83 80 77 74 -18 20 21 22 25 -30 29 27 26 24 -79 80 81 82 83 86 88 -83 81 78 77 76 73 71 -7 8 11 13 16 -28 27 26 25 22 -27 30 31 32 34 37 -87 86 83 81 80 79 78 75 -19 21 23 26 27 30 32 -38 40 43 45 48 51 52 55 -1 2 3 5 6 8 10 -24 21 19 16 14 -61 59 56 54 52 51 49 48 -39 37 34 32 30 27 24 -41 43 44 45 47 -86 85 84 81 80 79 76 74 -38 41 44 45 46 49 51 -50 53 54 57 58 59 62 65 -88 89 90 91 94 95 98 99 -73 76 78 81 83 85 -34 35 36 39 41 42 -26 29 30 33 34 -49 46 44 41 40 -66 69 70 73 75 76 77 78 -31 34 37 38 39 41 -58 60 63 65 66 68 -75 73 72 71 70 69 66 63 -68 71 73 76 79 81 -50 52 55 56 57 58 61 64 -98 95 94 93 90 -40 37 34 32 30 -73 76 77 80 81 84 85 -65 64 63 61 59 58 -52 53 55 57 58 60 61 63 -66 69 72 73 74 77 -77 76 73 71 68 67 66 63 -20 17 15 14 12 10 8 -69 67 65 63 62 61 59 56 -89 86 84 82 80 -46 47 48 51 53 54 56 -72 69 68 65 64 61 59 56 -33 35 37 40 43 46 48 -62 60 58 56 55 54 53 50 -99 97 96 93 92 90 88 -39 42 45 47 48 51 -74 75 76 79 81 82 83 86 -64 66 67 69 72 -38 35 34 33 30 -19 16 14 11 9 7 6 5 -66 65 62 60 57 55 -34 32 31 30 27 -76 75 74 73 71 -29 30 33 34 36 38 -33 36 39 41 44 -25 26 28 29 31 33 36 -13 11 8 7 6 4 -94 92 89 86 84 82 -54 51 50 49 46 44 43 41 -2 3 5 8 11 12 15 -30 31 34 36 38 -20 23 26 29 30 32 35 36 -61 64 65 68 71 -51 54 57 60 63 -21 22 23 26 27 30 33 35 -17 20 22 25 28 29 -44 42 39 36 34 31 30 29 -27 24 21 20 19 17 -32 30 29 28 26 24 21 19 -44 45 48 50 53 54 56 -89 86 83 81 80 78 75 72 -70 67 64 63 62 60 -52 53 54 57 59 -27 29 32 33 36 39 40 42 -32 34 35 36 39 42 45 48 -61 64 66 68 71 72 74 -33 30 28 27 24 23 20 -31 29 27 24 21 19 -21 20 19 17 15 12 -42 44 47 50 53 55 56 -77 79 80 83 86 87 88 91 -37 36 33 31 30 28 27 24 -13 16 19 22 25 26 29 -35 34 33 32 29 27 25 -50 52 53 56 57 59 -77 74 72 70 69 68 65 -88 91 92 93 96 -76 78 81 82 83 -64 66 68 69 70 73 74 75 -68 67 66 65 62 60 58 -57 56 55 52 50 48 46 -61 59 58 56 53 -15 12 9 6 5 3 -70 68 66 64 61 60 57 54 -75 78 81 83 84 85 87 -24 26 27 29 30 31 34 36 -53 56 59 60 63 66 -1 3 5 7 8 9 -89 87 84 82 79 78 76 75 -30 27 25 22 21 -37 36 34 31 30 29 -19 18 15 12 11 8 7 6 -60 58 55 54 52 50 48 -7 8 9 12 15 17 -89 90 93 94 96 -27 24 23 22 21 19 17 16 -22 20 19 18 15 14 12 -85 86 88 90 92 95 96 -38 39 40 42 45 -24 25 28 31 33 34 -70 69 68 67 65 63 62 -15 13 12 9 7 4 2 -49 48 45 42 41 -57 60 62 63 66 68 -31 34 37 38 40 -27 28 29 30 33 36 -36 34 31 30 29 28 27 -53 51 49 46 43 -95 92 90 88 85 83 -74 73 72 70 67 64 -23 20 17 16 14 13 -95 92 89 87 85 82 81 79 -36 35 34 32 31 30 29 -50 52 54 57 60 63 64 -58 61 62 63 64 65 68 70 -39 40 42 43 45 48 51 -85 84 81 79 77 74 -45 46 47 49 52 -15 16 17 20 21 22 -86 83 80 78 76 73 70 68 -51 54 57 59 62 -71 73 76 77 79 80 -68 69 72 74 77 78 79 81 -13 11 8 6 5 3 -50 52 53 56 57 59 60 -60 62 64 66 69 -80 83 84 86 88 -8 10 11 14 16 -43 46 47 50 53 56 -55 54 51 50 48 45 43 -66 68 71 74 75 -84 86 87 88 90 93 -38 37 36 33 30 27 26 -29 31 34 37 39 -12 10 9 6 4 -72 69 67 65 63 62 -23 25 26 29 30 32 -70 71 74 77 80 81 84 87 +]select(23,564)/$!where()>%mul(747,16)*why()mul(354,748)how()<?mul(29,805)where()mul(480,119)!,why()mul(685,393)(~'&[what()what()mul(376,146)-,<)do()^(mul(735,916)/~~,] what()where()mul(321,623)select()$#what() %#who()<*mul(363,643)where()[mul(360,266),:do()'mul(95,167)who()-select()@[{,)$select()mul(802,119) how()^: {from()mul(147,169)*select())^mul(488,194)$?when()mul(540,154)from()from()*^select()who()mul(8,750)where()mul(140,841)when()] >$(when()<:mul(428,793) where()from()how()/how()]*?mul(156,996))what()!,what()~@((mul(976,569)]-,>$-~%;mul(426,703)/mul(948,128)>+?+>?%select()*mul(477,567)why()%select()?!(@~how(){mul(182,79),mul(203,707)?[mul(186,170)select(283,626)*/*when()mul(130,392)')^&when(),[;mul(563,902)where()}*}<$/)how()mul(953,129)!!what()#what()!who()mul(852,652)~)+mul(973,163)$?why()]where()mul(158,596)when()@}what(29,454)mul(968,252)<'^'how()when()<*^mul(617,885)when()) +&;'mul(264,456)/mul(713,804),-mul(803,862)mul(575,310)[ why(527,60) )from()mul(475,876)from()when()*^$@:do()mul(557,2)'{^:-*what()mul(611,157) >- when()mul(894,415)!mul(856,397)from(),where()mul(13,373),!where(),do() {how()select()^:(#select(622,699)[mul(395,375)-##>+[what()?mul(535,15)/(];)mul(115,296)mul(201,604)^+[>+do()&:}how()/:mul(34,586)?where(375,645)?:-who()select()'why()>mul(389,101)don't()<^}who()mul(501,691)'select()mul(551,120),]?from(545,381)?*%~mul(492,926),:(who() {$ when()mul(348,721)'?/)?!what(784,670)mul(811,483): where()why()why()>$[when()do(),~*# {/mul(312,382),}*what(944,486)?^{+%mul(224,412)~why();?<]who()*^mul(199,783)what()from()@why()where()what()?select()(}mul(267,247) mul(126,337)select()mul(534,156)($%%}+*@mul(103,848):;'%mul(237,35)<&-where()mul(423,484),!]where()#!mul(281,866)select(750,996)(( *{<^%who()mul(437,982)}:mul(357,682)@< mul(124,834)}~mul(668,671)mul(787,282)</{[@+mul(669,479)&+who(324,639)when()mul(217,891)why()who(),who()!+~%who()from()mul(157,768)what()why()/mul(654,217)/?]+how()($mul(173,829))#(what()mul(78,373)(+{?&${([from()mul >from():where()'[mul(985,702)*{: -&where()how()mul(180,738)(from()@mul(240,76),[:'#!:select() mul(822,179)*#how()~!%!<mul(806;+from(28,284);@select()why()?what()how()#don't()select();;?how()[<mul(682,60)%+mul(166,261)!#<~who()'@who()/mul(991;mul(602,939)why()*how()mul(815 ~>who()who()how()where(184,532)#from() [mul(771,388)how()'~!^!@+mul(646,938)+,(({-mul(486,708)^%^from()-(;what()]mul(144,833)~why()%select()&<~how())mul(439,873)mul(677[[;{:?{>[ (mul(25,577))@:mul(727,412)why();?select()?what()};from()*mul(826,116)#*)/where()who();<@<mul(457,847)mul(145,20)^when()mul(547,892)}mul(368>!where()~when()where(597,883)-mul(835,616)'((where(808,96)',mul(649,224)&/ mul(35,958)who(871,394) :!-who()where()where()(mul(322,104^what()%,}[why()what()**who()mul(983,838)mul(614,657)what()&,mul(238,871)-{},select()>who()#>mul(943,599)select()select(558,572)?^who() <:mul(572,265))who()[why()!$,-mul(454,326)<mul(620,631)[who()]from()>mul(300,416)what()who()what()[;when()mul(786,381!<who()@}mul(588,123)mul(912}?-,&mul(757,105)*!!mul(646,183)~*^mul(208,472)^>&who()when()where(381,479) from()<!mul(374,508)',mul(936,836)&when()don't()<mul(87,618) +#-#$&?,mul(549,158):>!?$,what(),who()mul(429,727)}from(401,661)>{?<?:)mul(883,372);when()&who()mul(778,374)[+*+select(896,509):?(why()<mul(156,180)why(),don't()why()mul(186,452)-who()+don't()mul(801,495)what(226,680)( who()do()//~how()mul(810,508)}:from(){$where(285,907)'mul(101,25)?>%mul(518,766)-@who()!mul(276,326),select()%{mul(211,710)/mul(414,532)@!-,>mul(494,611)?%((@)[&who()mul(547/why()]who()*% $'who(675,908)mul(90,974)}mul(427,683)how()[:;mul(443,135)*^+~^{when()who()}[mul(579,135)@:who()mul(267,452)[&!;;where()$}who()mul(662,85)~>what()mul(724,771)$!mul(206,909)@^%mul)when()select(567,468)mul(260,632)who()what()</><}what()}@do()mul(866,137why()~)mul(13,816)^!*(mul(351,795)from()(?^ ;;,~'mul(313,157)?mul(222,186)!> &how()$mul(558,129)how()[select()from()'/&when()[^mul(927,606)@?<+how()-}(mul(749,285)!![%~>mul(919,804)+&-->where()!&$/mul(889,472):why() <]++from():)mul(597,828)!*~@mul(61,536)(why()what(): >why()*mul(50,308)mul(980,618){-! ?*why() *mul(506,77)#/where()^~';who()%<do(){&{mul(540,5)%&'mul(128,695)!mul(96,956):(${'where()<(mul(45,167)mul$?what()>who():mul(11,806)mul(226,600)?how()% /{//mul(601[><<&mul(70,238)select(176,735)mul(447,978)(^#mul(583,880)@[<mul(509,562)[&why(){-select(513,478)who()~mul(966,836when(763,296)](?-mul(131,634)from(261,473)%mul(212,467)(why()mul(876,253~mul(426,669)&select()>mul(722,873)>mul(110,728)/+mul(948,566)where(760,139)[ -*why()-mul(92*,:-$how(),where()<mul(873,257)select()/!*don't()&#?from()why()where()%}mul(210,425)how()--mul(819,836where()<!why()'>select(),+mul(954,569)&<what()$(&-'[mul(514,751)?#);#mul(570,718)where()mul(369,56)mul(701,888)select()when()why()when(932,357)mul(954,415)select()^!&mul(975,208)<select()when()#}mul(123,114)#?/where()'-]do()>?#+(mul(482,680)]mul how()&what()%-mul(455,447)-from()+>?[/where()!:mul(502,951)?~mul(953,617)[/]&>^when()mul(234,738who(134,419))&$<what()mul(351,35)!mul(450,397)~@why()/$why()mul(315,592)?('$)]mul(361,911),+ $$, @?mul(648,348)why()*(~mul(741,895)]don't()who()/$<from()<what()@where()mul(914?!from()select()mul(221,704)mul(869,570)']/ '&why() ;who(970,163)mul(891,301{what()what()who()?$])mul(304,61)[,mul(380,797):'mul(134,245<}>-${)when()#why()/mul(266,78)&- ;mul(336,100)?$'#{'~:^mul(963,726)/&@mul(738,99){where(903,414)how()<mul(433,254)mul'%who()*where()mul(612,425):how()%mul(925,380)'('#/:mul(590,924)&where()%'mul(629,151)**;%<%?when()mul(231,925)mul(535,69),mul(695,901),?{+-~select()@mul(173,181)#what()/<^-select(),]what()mul(478,661)how()'/mul(269,398)}?$mul(203,769):select()^<<,^-mul(440,541)( (why()mul(264,622));where()mul(53,921)when()]mul(802,877)where()&?when()mul(24,441)where()mul(83,37)/where()--/how()'mul(278,236)]from(380,409)mul(486,676)-+]<mul(332,224)%#~'$$from(){how()(mul(786,79),>>)mul(249,770)$&@ ]from()$how()!select(521,465)mul(617,783)}<>):[,select(333,996)mul(416,179)[[don't()$]>why()@:mul(148,463)from()-do()when()-/how()when()&from(930,269)[mul(10,173)#mul(613,997)(<where()^< mul(359,962)where()#what()what(), mul(276,357)!who()){!where()'}'mul(860,748) +#(^(who()what():+don't()where()who()-,mul(407,102))~^how()<<$&from()mul(640,494)@who();!where()'do())~>>when(); *'@mul(724,407)don't()-when()why(533,992),')(:mul(472,652)?mul(350,214)!>where(401,417)/from()$where()mul(108,897)*where()<%select();,$mul(177,623)mul(674,586);mul(188,601)where()&/]mul(892,181)$from()?mul(904,15)why()(from()select()?@{?mul(832,651)<)mul(485,621)?%from()^);from();-who()mul(964,655);((select()mul(950,896)mul(103,475)when())/mul(165,476)(*},)where()!(@mul(417,206)&]?why()%-{[select(),mul(162,447)don't()why()!(/# from()~!mul(794,412)':&?why()mul(419,168);&who()%]who()mul(689,382)who(754,484)select())@)#[('mul/#/,select() why()??&mul(868,352)!from()!who(201,267)what(971,755)mul(245,790):!(^~&^where()--mul(334,775),why()why() when()'@?mulwhen()$?!]- '~@)mul(874,152)when()mul(771,202)(>@~;who()/]@mul(331,997)] select()%&mul(230,638)<%/mul(729,194)when()why()-@-select()select()'!&mul(669,652)/@%where()*;mul(799,156)from(){%why()mul(666,169)-#mul(381,557)&'??>+/>[what()mul(534,338)(mul(631,275),#[{when()~select()mul(847,310)when()]~}where()what(661,551)from()!mul(321,129);$where()@ why()where(616,873)-~(mul(888,479)who(),mul(229,502)])when()don't() mul(246,553)why()?select()',*?mul(242,385)}}where()mul(522/why();mul(445,61)mul(746)$why()from()don't()+mulfrom()#mul(521,245)]%?]}mul),[who()where()mul(784,56)!why(): when(893,294)&[mul(373,342)<$ *! {[why()mul(513,340)how()}where()'[^)^mul(967,981)^from(740,8)^{what()')mul(244,532)+ who()/*mul(686,40)>mul(178,177),][)-<([mul(595,777)<-how()>(,)}mul(210,328)?why() )$why()where()<what()mul(252,597),when()}[!mul(940,426)select()[[mul(71,619)%select()~::%where()mul(811,55)[from():mul(442,618) how()select()~mul(569,19&why()!select(){]$<[what()mul(71,211)/%!]mul(146,583)]from()?when(610,567)^from():where()select()don't()mul(453,186){;%mul(667,596),/^{,(select()mul(387,262)%select()'mul(720,489)'#*$+/what()-*/mul(715,93)^{who(564,37)[mul(440,43)-who()what()-{who()]mul(546,613)??^~&select()mul(69,463)how(){+(<mul(255,367)]~![what(){who()don't()-from()'why()>/['*%mul(654,641)select()$[select()mul(620,43)$from()!mul(573,638)<,#/>why(451,392)/how()mul(450,634) ,%@&,don't()select()~~}%select()when()@%<mul(142,868)]:?:#@}-mul(723,185)$mul(305,502)>@+!^%mul(621,328){@{)when()#)who(685,504)mul(179,100)select(){from()why()]>-mul(94,187);mul(509,291)-how()when()do()why()@) how()select()+mul(379,538)mul(830,641), /&+-@mul(180,491)how():why()!!'%%where()mul(266,732)when();select():+how()(;%mul+who()}{+do()mul(575,752))<what()~(~(>how()mul:&from()>who(854,820)mul(850,918)&select()(}+}mul(782,495))<'?(>){where(),mul(957,190)/when()what()who()mul(352,79)why()'mul(652,626)mul(973,815)>[)-];@'mul(327,736)$@mul(221,196)~;>,[what()mul(170,288)what()~:$<don't()[-]what()$mul(115~()mul(65,844)/mul(152,544)>what()'from(468,557)%&>~who()how()mul(847,27){where()?'mul(736,195)mul(663,417)%mul(301,538)don't()what()select();+[how()?+}/mul(271,885)[when()] select()mul(251,286)],{-why()how()-% what()mul(664,742)from()>^!&mul(583,557)%#{}where()why()))don't()[^[mul(636,736)mul(733,889)mul(415,907)#what()what()from()where()mul(746,170)what()how()%who()/mulhow()don't()*'why()[select(769,463)$'/from()mul(520,584)*who()from()~]>who(862,907)why()mul(423,117)why();mul(100,371)!@<{from()mul(434,31) +*why(816,889)& &:!#!/usr/bin/perl/<$!{ (mul(142,115)where()[}/'when()mul(444,725 ~*:why()& from()when(493,415)&mul(863,234)<@?$/when()'+,mul(722,893),%'don't()~where()why()^,;%;%mul(823,490})$<*$#mul(101,716)&from()%@who() what()mul(881,570)who()@+(/@mul(676select()when()*;@@]why()#mul(315,278)[%'select()[{[mul(237,596)mul(782%^<^+:/:~how()when()mul(565,260))~where()??mul(4,427)'where()(when()?-}select(314,151)mul(361,206)-what()!!mul(575,211)!@}select()% ;mul(996,776) how()!#'+)what(861,201)<from()mul(803,47)how()@[^+who()[from(334,635)when()mul(239,900)^what() mul(129,262)$}what()?when()from()when(){};mul(433,265)when()[:}who()when()from():<mul(653,369)mul(299,195)+when()mul(885,839)}~((]:,)mulselect() %~ ^&}why()mul(335,155)select()&~<mul(775,440)mul(599,234)$#why(64,305)!!what()(+<+do(),-mul(339,978) who()select()];~!:^from()mul(404,428)mul(148,78)who()select()>who()]when()how()what()#mul(862,926)when()*;#:['mul(189,238) :[how()who(971,4)~+<(mul(481,269)<from()what(509,537)from() what()mul(97,894)/{where()}mul(164,658)<<mul(459,615)@>%mul(632,943)from(){{}'why()who(); select()mul(364,748){;,mul(214,990)from(){>$?:why())mul(206,633)where()what()]*@<$who()}+mul(14,141))mul(822,373)]? how()[from(){mul(978,657{,%]{^mul(688,489)##![why(){}do()#why(),];)when()who()mul(305,206)<]<~ ]don't()?mul(304,632) [mul(291,282)+}{when(),from()#mul(662,53)}mul(5,779)#mul(111,303)where()+!<*'%how(960,285);>mul>mul(852,693)%;)*$':;]who()mul(249,548)@)select()]mul(387,459):/'when()$-[>!mul(112,988)from()@~> $mul(191,655);mul(79,498)~)<@/$@;when()#mul(513,202)][*how()$[from()mul(224,73)&'-&,why()@#from()mul(737,275)who()<mul(739,419)}%-)*'why():mul(842,699)why(251,569)-)why()who()when()>-[from()mul(816,564)mul(66,866)'from(239,497)how()>>%/<%who()mul(846,687)how()how(854,968)<mul(768,457who()>don't()@@[*>where()!mul(268,28)+[#(? -mul(398,631)&?}}^-$&~mul(283,82)@what()don't()<mul(837,666)%[~,$+ mul(31,972);#mul(850,483)why():from()?) ]mul(58,370)%mul(363,410);'+({]mul(617,613)([*/from()^from(885,5)who()mul(876,980)where()~mul(749,501)select()}> what()mul(720,734),? who()mul(380,889)%+select())*how()how();%[mul(48,988)$;mul(968,247)* mul(884,462)*#from()>mul(366}what()]((<<what()-don't()~how(432,457)$select()(mul(177,831)mul(4,455)@select()from()mul(729,440)^#/+how()[&mul(688,376)how()&mul(211,599)$select()'who()how()?who();mul(192,204)}>+mul(133,244)*'{-where()mul(729,105)how(619,497);from()+from()when()when()when()from()mul(900,829)$mul(83,600)*how()why()mul(434,610)don't())(?@^,mul(691,992)}^:why(784,454)don't()$&#mul(892,279);':what(){~when()what(361,846)']mul(720,864),why()where()mul(303,491)&;[what()mul(720,732)$~,who();/!mul(407,549)-select()!mul(127,272)-%['???select()what(412,125)]don't()&where()]mul(322,71)@/+select()why()$<who()>?mul(650,186)&@>@[:![mul(887,229)why()]select(298,963)where()when()?where(992,533):mul(753,118)[what()what()$@(what()]mul(683,687)<why() &;>@[mul(471,355)why()who()$>^?how()mul(271,372)mul(68,707)#when(358,219)'&who()mul(811,52)who()<-:#(from()~mul(160,946)!'@>?[;what()mul(206,444)[$why();why()&:mul(299,200)?what()[what() (+mul(298,431)<$^'(mul(822,566)why()when()+how()-#]]?mul(401,194),mul(320,99)when()*$where()!+]mul(635,430)mul(474,531)%' <how(){mul(915,913){what()select()from(367,196)>}mul(896,524) +@who()$don't()who()#&##mul(245,843)mul(707,597):!,mul(864,931);$mul(605,621)&@mul(700,646)>%what(225,888)!%who()[:select()mul(297,15)]^%~]who()mul(87,793)?+{<-where()%mul(518,305)why()+,(~ /!mul(588,968)mul(295,237):-,}%:{+:who()mulwhat(){~*~/'<>mul(590,124)/mul(719,423)))?:+select()mul(902,901)when(){>mul(455,460)$,what()(&{}how()*{mul(24,765)/]mul(529){[#+>/select()?(+mul(19,771)where()+/+mul(380,138)who()when(){from()@mul~$/don't()))select()mul(333,659)< select(213,174)*!select()mul(310,90)mul(494,223)!$when()~how()@mul(656,481)!</;mul(985,195)when() /(]who()^[how(){mul(156,227)[mul(475,974)/@:;,mul(981,216):?!&%^+*mul(243,273)#}<&where()mul(510,175)>*!$mul(705,700)mul(7,569)!#;%}> '?mul(324,975) ^/who()$~^ from();do()~!mul(883,226)]mul(660,990)*select()select()[#}!^mul(426,750)when()')#(when()$select()#mul(790,641)what(196,61)&?where()what()mul(751,795)why()#what()/((*who()select(465,475)'mul(633,76)~%&don't()}/why()where()mul(320,249)who()^{how();?'mul(239;;[}]*(;//mul(51,601)%/~%+!'!how(665,519)mul(611,916)what();mul(174,972)when()-where()-how()('do()mul(108,242)?+mul(870,660)]when()%what()?<:mul(635,416)why(924,420)[<$from()>how(260,907)#where()mul(236,788),,@<do()/who()]why()),mul(104,324),,+}<why()mul(81,926)?mul(703^/$~[(what()mul(77,726)[<%}{how()mul(56,385)$from()[,#when(529,538)where()]~why()mul(497,356)[]mul(870,813)/)/where()-mul(537,196)select()where()++%+where(){do();mul(584,253)when()&who(),select()mul(788,391)don't()}how()&{~}where()mul(157,737)[mul(908,38)mul(818,655['+,~mul(773,541)what()(, >?from())>mul(97,620):select()!+mul(899,189):!}mul(566,974)'why()select()*where()what())why()~why()mul(908,528):)}^mul(71,100)from(296,15)when()from())&from()#how(869,278)mul(628,153)how()mul(765,691)*mul(186,21)how()/mul(487,725)do()##/::from(){what()%)mul(110,152)*&**,$ from()*mul(992,213)[*/!~mul(797,726)-from()mul(969,578)when(112,655)*how()when(),where()'(mul(440,56))*{'(from()-&mul(113,81)^^what()#!))')[mul;~<mul(277,301)#,,%from()mul(121,117)]+$$mul(15,795)[@select(),!how()'mul(575,181)^&mul(178,328)<:select()#mul(801,216)who()what();{where(594,478)<&why()mul(431,843)>mul(147,629)!@<#&^]@select()mul(993,659),{ mul(254,347<<>}why()(who()>!)how()mul(518,738)what(29,303)from()mul(160,896)do(){/;?what()where()where()how()mul(173,649)</:mul(463,794)from()mul(480,942)-where()($%$~~mul(731,892)&how()'}mul<,mul(948,47)<{@how()from()]mul(219,441)''~@}(mul(383,202) ${&}<?select()who()>mul(969,370$~>mul(679,266)how()>@):@where()mul(206,774))[from()what()where()mul(950,797-) ,^%%mul(996,344)what();select()#mul(332,248)*!'<&~mul(408+how()mul(114,169)$<who() &+^mul(692,942)do(),[$@!how(684,237)-{mul(120,876)how()}%/&mul(761,409);who())who()#where():*mul(518,173)select(675,835)$ ^why()}where()/mul(405,527)from()< ^who()how()what()from()how()!mul(950,134)what()?<^mul(814,585)from())who()mul(816,366)+~-+when()what()why(262,438)what(420,569)mul(105,532)!'%mul(151,891)how()@*(:where()!(mul(178,962)mul(751,447)/[+/-mul(851,764)mul(588,654)mul(882,76)'where()$~(where()-mul(526,650){(}*#; :)who()mul(29,13)?}:what()who(520,6)/mul(56,722) +mul(946,420)~)where(719,224)mul(718,516)select()/{# when(),*?<mul(400,748)}who()where()select(308,170):]from(2,72)mul(357,947){what()*how(){*where()what()select()mul(430,803)::from()-*'$where()from()mulwhen(660,983)mul(445,455)mul(490,913)select()#*mul(646,393)>@~select()@~who()mul(901,342)*mul(499,634)%!mul(996,710)~/$}select()mul(8,949)$;(!};from(): mul(860,166)(@-from()'',mul(739,160)$%who(265,676) mul(988,26) ,+/mul(293,416)where()+#}-from(){(@(mul(215,463)mul(152,776)+*]'#'mul(447,726)how()-#}select()what()select(892,487)% mul(182,115)^$<(why()mul(335,275)when(801,993)];select()}'>^how()>do()mul(704,863)+why()'*&mul(709,745)who(){select()mul(17,822)}from()!+;!+,where()]mul(280,107)~?}how()/'(?who()mul(288,599)%what() ]$)mul(463,772)@mul(992,279)what()!:why()>>who() (mul(348,687)*]mul(477,896)when(47,10)&where()?what()%[mul(804,970)from()from()select()+what()[who()-?mul(166,890)&-^mul(892,532)mul(905,17)*)/]>@ {*:mul(361,902)[$]~*mul(629{*<)how()$from()#({mul(924,910)'who()why()'&)}mul(322,152) &mul(503,282)^ )/what()what()%mul(678,160)when()!?&#<%^*mul(661,59)(*mul(936]'<what()what()![[{)!mul(572,448)]#!from()mul(509,887)^&?how()from()?why()]mul(393,953)don't()@what()what()why()~,+*when()mul(546,677)when()^where(292,766)mul(968,760-&!why()mul(657,456)select();~mul(527,553):how()#~#mul(639,12)>;)];)who()&&mul(437,929)who()mul(298,239)<(%:>}do()mul(727,688)~(<)who(846,894)mul(720,201)!$@)}mul(139,406)~!$mul(123,17)&select(564,607)(]<mul(407,428);^):{+how()mul(606,64):)mul(652,400)%:;who()/][mul(850,192)mul(184,269)why()< }!@*<}mul(655,422)>:who()where();^//mul(905,342)&%)mul(185,967)--~+$ when()@mul(594,891)#:[%,;mul(641,786),@>'how()don't(),mul(185,960)(mul(702,204)]]!(%$++# mul(24,904)!mul(109,193)+[{when()mul(579,493)%where():!mul(473,16)$from()]mul(33,997)mul(104,325)'mul(486,457)select()who()<-who()]&mul(720,711)&do()how()!/!%*^^mul(239,525),from()select()mul(77,963)how()]where()<who()'-~/:mul(856,16);<mul(356,792)+/(where():}}mul(15,617)mul(878,763))~when()where()%#(select():mul(427,938)^where()^<mul(208,838)*)who()*'< %mul(982,594)-%mul(683,977)-+;,mul(541,415)~why(){*(what()$,when()mul(648,533) when()'?%<*how()do();how(108,300))when()mul(291,292)mul(65,4):from()&mul(466,215)#%&;[,select()<what()do()+select(){?{~where()'what()mul(637,530)mul(75,335),;)[+%mul(738,984)(select()/{what()when(773,881)mul(916,756)?:]:!^mul(991,341)mul(145,20)mul(279,825)[](when(879,87)({<#)how()mul(326,199)#:{what()what()<}:where()mul(112,738)when()<select(930,412)from()mul(887,573)^-,from()mul(795,440)mul(94,274)$when()(select()how()$when():mul(841,178)how()$mul(127,186)!:~/-where()<what(10,606)mul(291,547):mul(21,379)&^when()what()+/mul(172,574)@+@what()$'why()~mul(765,254)where()mul(448,944),>{what()+mul(452,303);/~mul(55,517)&>^~when()-mul(949,308)(@~@what()@**how()mul(185,245)+}how() select()mul(89,379)~&!@ where()-) diff --git a/src/main.rs b/src/main.rs index 27d0ce1..710b2ab 100644 --- a/src/main.rs +++ b/src/main.rs @@ -27,117 +27,78 @@ extern crate test; pub mod util; use atools::prelude::*; -// use hinted::HintExt; -pub use util::prelude::*; - -#[no_mangle] -fn check(x: &[i8]) -> bool { - if x.len() > 8 { - unsafe { std::hint::unreachable_unchecked() } - } - let state = unsafe { x.first_chunk::<2>().map(|[a, b]| a < b).unwrap_unchecked() }; - x.array_windows::<2>().all(|[a, b]| match state { - true if !(1..=3).contains(&(b - a)) => return false, - false if !(1..=3).contains(&(a - b)) => return false, - _ => true, - }) +use logos::{Lexer as RealLexer, Logos, SpannedIter}; +#[derive(Logos, Debug, PartialEq, Clone)] +#[logos(skip r"[\n\s]+")] +#[allow(dead_code)] +pub enum P2 { + #[token("do()")] + Do, + #[token("don't()")] + Dont, + #[regex(r"mul\([0-9]+,[0-9]+\)", |lex| lex.slice().μ(',').array().map(|x| x.as_bytes().iter().filter(|x| x.is_ascii_digit()).fold(0, |acc, x| acc * 10 + (x -b'0') as u32)))] + Mul([u32; 2]), } -pub fn run(i: &str) -> impl Display { - let mut items = [0; 8]; - i.行() - .filter(|x| { - let mut len = 0; - let mut s = 0; - for &b in *x { - match b { - b' ' => { - C! { items[len] = s as i8 }; - len += 1; - s = 0; - } - b => s = s * 10 + (b - b'0'), - } - } - C! { items[len] = s as i8 }; - let slice = C! { &items[..len + 1] }; - check(slice) - // (0..items.len()).any(|n| { - // let mut items = items.clone(); - // items.remove(n); - // check2(&items) - // }) - }) - .count() +#[derive(Logos, Debug, PartialEq, Clone)] +#[logos(skip r"[\n\s]+")] +#[allow(dead_code)] +pub enum P1 { + #[regex(r"mul\([0-9]+,[0-9]+\)", |lex| lex.slice().μ(',').array().map(|x| x.as_bytes().iter().filter(|x| x.is_ascii_digit()).fold(0, |acc, x| acc * 10 + (x -b'0') as u32)))] + Mul([u32; 2]), } -#[no_mangle] -fn check_pof(x: &[i8]) -> Result<(), u8> { - if x.len() > 8 { - unsafe { std::hint::unreachable_unchecked() } - } - let state = match unsafe { - x.first_chunk::<2>() - .map(|[a, b]| a.cmp(b)) - .unwrap_unchecked() - } { - std::cmp::Ordering::Equal => return Err(0), - std::cmp::Ordering::Greater => false, - std::cmp::Ordering::Less => true, - }; - // windows at home 😔 - for i in 1..x.len() as u8 - 1 { - let [a, b] = util::nail(&x[i as usize..]); - match state { - true if !(1..=3).contains(&(b - a)) => return Err(i), - false if !(1..=3).contains(&(a - b)) => return Err(i), - _ => (), - } - } - Ok(()) +pub use util::prelude::*; + +pub fn p1(i: &str) -> impl Display { + P1::lexer(i) + .filter_map(Result::ok) + .map(|P1::Mul(a)| a.product()) + .sum::<u32>() + // let re = regex::Regex::new("mul\\(([0-9]+),([0-9]+)\\)").unwrap(); + // re.captures_iter(i) + // .map(|find| { + // reading::all::<u32>(find.get(1).ψ().as_str().as_bytes()) + // * reading::all::<u32>(find.get(2).ψ().as_str().as_bytes()) + // }) + // .sum::<u32>() + + // i.行() + // .filter(|x| { + // // let x = x.κ::<u64>().collect_vec(); + // }) + // .count() } -#[no_mangle] -pub fn p2(i: &str) -> impl Display { - let mut items = [0; 8]; - i.行() - .filter(|x| { - let mut len = 0; - let mut s = 0; - for &b in *x { - match b { - b' ' => { - C! { items[len] = s as i8 }; - len += 1; - s = 0; - } - b => { - s = s * 10 + (b - b'0'); - } - } - } - C! { items[len] = s as i8 }; - let slice = C! { &items[..len + 1] }; - match check_pof(slice) { - Ok(()) => true, - Err(i) => { - let i = i as usize; - let mut place = [0i8; 7]; - macro_rules! rmv { - ($i:expr, $si: expr) => {{ - place[..$i].copy_from_slice(&slice[..$i]); - let put = &slice[$si..]; - place[$i..$i + put.len()].copy_from_slice(put); - &place[..slice.len() - 1] - }}; - } - check(rmv!(i, i + 1)) // [1, 2, >i<, 4, 5] - || check(rmv!(i + 1, i + 2)) // [1, 2, i, >4<, 5] - || (i > 0 && check(rmv!(i - 1, i))) // [1, >2<, i, 4, 5] - } +pub fn run(i: &str) -> impl Display { + let mut state = true; + P2::lexer(i) + .filter_map(Result::ok) + .map(|x| { + match x { + P2::Mul([a, b]) => return a * b * state as u32, + P2::Do => state = true, + P2::Dont => state = false, } + 0 }) - .count() + .sum::<u32>() + // let re = regex::Regex::new(r"mul\(([0-9]+),([0-9]+)\)|don't\(\)|do\(\)").unwrap(); + // let mut on = true; + // re.captures_iter(i) + // .map(|find| unsafe { + // match find.get(0).unwrap_unchecked().as_str() { + // "don't()" => on = false, + // "do()" => on = true, + // _ if on => { + // return reading::all::<u32>(find.get(1).ψ().as_str().as_bytes()) + // * reading::all::<u32>(find.get(2).ψ().as_str().as_bytes()) + // } + // _ => (), + // }; + // 0 + // }) + // .sum::<u32>() } fn main() { @@ -147,9 +108,9 @@ fn main() { // s.push_str(i); // } // std::fs::write("src/inp.txt", s); - // println!("{}", p1(i)); + println!("{}", p1(i)); println!("{}", run(i)); - println!("{}", p2(i)); + // println!("{}", p2(i)); } #[bench] @@ -159,7 +120,7 @@ fn bench(b: &mut test::Bencher) { } #[bench] -fn p21(b: &mut test::Bencher) { +fn bench2(b: &mut test::Bencher) { let i = boxd(include_str!("inp.txt").trim()); - b.iter(|| p2(i)); + b.iter(|| run(i)); } |