#902050 (Rust) No.2417 Div Count

• 問題: No.2417 Div Count
• ユーザー: Sarievo
• 提出日時: 2023-08-12 13:50:41
• 言語: Rust (1.77.0 + proconio)
• 結果: AC
• 実行時間: 8 ms / 2,000 ms
• コード長: 48,213 bytes
• コンパイル時間: 13,009 ms
• コンパイル使用メモリ: 378,200 KB
• 実行使用メモリ: 5,248 KB
• 最終ジャッジ日時: 2024-11-19 16:23:08
• 合計ジャッジ時間: 14,341 ms
• ジャッジサーバーID （参考情報）: judge1 / judge5

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 5,248 KB
testcase_01	AC	1 ms; 5,248 KB
testcase_02	AC	1 ms; 5,248 KB
testcase_03	AC	1 ms; 5,248 KB
testcase_04	AC	1 ms; 5,248 KB
testcase_05	AC	1 ms; 5,248 KB
testcase_06	AC	1 ms; 5,248 KB
testcase_07	AC	1 ms; 5,248 KB
testcase_08	AC	1 ms; 5,248 KB
testcase_09	AC	1 ms; 5,248 KB
testcase_10	AC	1 ms; 5,248 KB
testcase_11	AC	1 ms; 5,248 KB
testcase_12	AC	0 ms; 5,248 KB
testcase_13	AC	1 ms; 5,248 KB
testcase_14	AC	1 ms; 5,248 KB
testcase_15	AC	1 ms; 5,248 KB
testcase_16	AC	1 ms; 5,248 KB
testcase_17	AC	1 ms; 5,248 KB
testcase_18	AC	0 ms; 5,248 KB
testcase_19	AC	1 ms; 5,248 KB
testcase_20	AC	1 ms; 5,248 KB
testcase_21	AC	1 ms; 5,248 KB
testcase_22	AC	1 ms; 5,248 KB
testcase_23	AC	1 ms; 5,248 KB
testcase_24	AC	1 ms; 5,248 KB
testcase_25	AC	1 ms; 5,248 KB
testcase_26	AC	1 ms; 5,248 KB
testcase_27	AC	1 ms; 5,248 KB
testcase_28	AC	1 ms; 5,248 KB
testcase_29	AC	1 ms; 5,248 KB
testcase_30	AC	1 ms; 5,248 KB
testcase_31	AC	1 ms; 5,248 KB
testcase_32	AC	3 ms; 5,248 KB
testcase_33	AC	2 ms; 5,248 KB
testcase_34	AC	1 ms; 5,248 KB
testcase_35	AC	4 ms; 5,248 KB
testcase_36	AC	3 ms; 5,248 KB
testcase_37	AC	3 ms; 5,248 KB
testcase_38	AC	8 ms; 5,248 KB
testcase_39	AC	4 ms; 5,248 KB
testcase_40	AC	2 ms; 5,248 KB
testcase_41	AC	2 ms; 5,248 KB
testcase_42	AC	1 ms; 5,248 KB

ソースコード

// {{{ My social:
// YouTube: https://www.youtube.com/@Sarievo
// SoundCloud: https://soundcloud.com/sarievo
// Twitter: https://www.twitter.com/sarievo
// }}}

fn solve() {
    prepare!();
    sc!(n, k);

    let mut res = 0;
    let e = n - k;
    let mut i = 1;
    while i * i <= e {
        // dg!(i * i);
        if e % i == 0 {
            if i > k {
                res += 1;
            }
            if e / i > k && e / i != i {
                res += 1;
            }
        }
        i += 1;
    }

    out!(res);
}

// <><><><> Lib Codes <><><><>

#[allow(unused)]
use sarievo::{
    segtree::{
        identity::*,
        monoid_actions::{Additive, Max, Min},
        Segtree, Segtree2D,
    },
    *,
};
#[allow(unused_imports)]
use std::{
    cmp::{max, min, Ordering, Reverse},
    collections::{
        btree_map, hash_map, BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque,
    },
    vec,
};
// {{{ Lib Codes
mod sarievo {
    use super::*;
    // {{{ Range
    pub fn get_range<R: std::ops::RangeBounds<usize>>(range: R, n: usize) -> (usize, usize) {
        use std::ops::Bound::*; // https://doc.rust-lang.org/stable/std/ops/enum.Bound.html
        let l = match range.start_bound() {
            Included(l) => *l,
            Excluded(l) => l + 1,
            Unbounded => 0,
        };
        let r = match range.end_bound() {
            Included(r) => r + 1,
            Excluded(r) => *r,
            Unbounded => n,
        };
        (l, r)
    }
    // }}}
    // {{{ Segment Tree
    #[allow(unused)]
    pub mod segtree {
        use super::*;
        // {{{ Identity
        use self::identity::*;
        pub mod identity {
            // Additive Identity
            pub trait Zero: Sized {
                fn zero() -> Self;
            }
            // Multiplicative Identity
            pub trait One: Sized {
                fn one() -> Self;
            }
            #[macro_export]
            macro_rules! zero_one_impls {
                ($({$Trait:ident $method:ident $($t:ty)*, $e:expr})*)=>{
                    $($(impl $Trait for $t{fn $method() -> Self { $e } })*)*
                };
            }
            zero_one_impls! (
                {Zero zero u8 u16 u32 u64 usize i8 i16 i32 i64 isize u128 i128, 0} {Zero zero f32 f64, 0.}
                {One one u8 u16 u32 u64 usize i8 i16 i32 i64 isize u128 i128, 1} {One one f32 f64, 1.}
            );
            // Associative Identity
            pub trait Bounded: Sized {
                fn maximum() -> Self;
                fn minimum() -> Self;
            }
            macro_rules! bounded_num_impls {
                ($($t:ident)*)=>{
                    $(impl Bounded for$t{
                        fn maximum() -> Self { std::$t::MAX }
                        fn minimum() -> Self { std::$t::MIN }
                    })*
                };
            }
            bounded_num_impls!(u8 u16 u32 u64 u128 usize i8 i16 i32 i64 i128 isize f32 f64);
        }
        // }}}
        // {{{ Magma
        use self::magma::*;
        pub mod magma {
            pub trait Magma {
                type T: Clone;
                fn operate(x: &Self::T, y: &Self::T) -> Self::T;
            }
            pub trait Associative {}
            pub trait Semigroup: Magma + Associative {}
            impl<S: Magma + Associative> Semigroup for S {}
            pub trait Unital: Magma {
                fn unit() -> Self::T;
            }
            pub trait Monoid: Semigroup + Unital {
                #[doc = " Binary Exponentiation: xⁿ = x ×  × x"]
                fn pow(mut x: Self::T, mut n: usize) -> Self::T {
                    let mut ret = Self::unit();
                    while n > 0 {
                        if n & 1 == 1 {
                            ret = Self::operate(&ret, &x);
                        }
                        x = Self::operate(&x, &x);
                        n >>= 1;
                    }
                    ret
                }
            }
            impl<M: Semigroup + Unital> Monoid for M {}
        }
        pub mod monoid_actions {
            use super::*;
            use std::{marker::PhantomData, ops::Add};
            pub struct Additive<T: Clone + Zero + Add<Output = T>>(PhantomData<fn() -> T>);
            impl<T: Clone + Zero + Add<Output = T>> Magma for Additive<T> {
                type T = T;
                #[inline]
                fn operate(x: &Self::T, y: &Self::T) -> Self::T {
                    x.clone() + y.clone()
                }
            }
            impl<T: Clone + Zero + Add<Output = T>> Unital for Additive<T> {
                #[inline]
                fn unit() -> Self::T {
                    Zero::zero()
                }
            }
            impl<T: Clone + Zero + Add<Output = T>> Associative for Additive<T> {}

            pub struct Max<T: Clone + Bounded + Ord>(PhantomData<fn() -> T>);
            impl<T: Clone + Bounded + Ord> Magma for Max<T> {
                type T = T;
                #[inline]
                fn operate(x: &Self::T, y: &Self::T) -> Self::T {
                    x.max(y).clone()
                }
            }
            impl<T: Clone + Bounded + Ord> Unital for Max<T> {
                #[inline]
                fn unit() -> Self::T {
                    Bounded::minimum()
                }
            }
            impl<T: Clone + Bounded + Ord> Associative for Max<T> {}

            pub struct Min<T: Clone + Bounded + Ord>(PhantomData<fn() -> T>);
            impl<T: Clone + Bounded + Ord> Magma for Min<T> {
                type T = T;
                #[inline]
                fn operate(x: &Self::T, y: &Self::T) -> Self::T {
                    x.min(y).clone()
                }
            }
            impl<T: Clone + Bounded + Ord> Unital for Min<T> {
                #[inline]
                fn unit() -> Self::T {
                    Bounded::maximum()
                }
            }
            impl<T: Clone + Bounded + Ord> Associative for Min<T> {}
        }
        // }}}
        // {{{ Segtree
        #[derive(Clone, Debug)]
        pub struct Segtree<M: Monoid> {
            n: usize,
            tree: Vec<M::T>,
        }

        impl<M: Monoid> From<Vec<M::T>> for Segtree<M> {
            fn from(v: Vec<M::T>) -> Self {
                let n = v.len();
                let mut tree = vec![M::unit(); n * 2];
                tree[n..].clone_from_slice(&v);
                for i in (1..n).rev() {
                    tree[i] = M::operate(&tree[i << 1], &tree[i << 1 | 1]);
                }
                Self { n, tree }
            }
        }

        impl<M: Monoid> Segtree<M> {
            pub fn new(n: usize) -> Self {
                vec![M::unit(); n].into()
            }

            fn __propagate(&mut self, mut k: usize) {
                k >>= 1;
                while k > 0 {
                    self.tree[k] = M::operate(&self.tree[k << 1], &self.tree[k << 1 | 1]);
                    k >>= 1;
                }
            }

            pub fn assign(&mut self, mut k: usize, x: M::T) {
                k += self.n;
                self.tree[k] = x;
                self.__propagate(k);
            }

            pub fn update(&mut self, mut k: usize, x: M::T) {
                k += self.n;
                self.tree[k] = M::operate(&self.tree[k], &x);
                self.__propagate(k);
            }

            pub fn get(&self, k: usize) -> M::T {
                self.tree[k + self.n].clone()
            }

            pub fn fold<R>(&self, range: R) -> M::T
            where
                R: std::ops::RangeBounds<usize>,
            {
                let (l, r) = get_range(range, self.n);
                let mut l = l + self.n;
                let mut r = r + self.n;
                let mut lv = M::unit();
                let mut rv = M::unit();
                while l < r {
                    if l & 1 != 0 {
                        lv = M::operate(&lv, &self.tree[l]);
                        l += 1;
                    }
                    if r & 1 != 0 {
                        r -= 1;
                        rv = M::operate(&self.tree[r], &rv)
                    }
                    l >>= 1;
                    r >>= 1;
                }
                M::operate(&lv, &rv)
            }

            pub fn len(&self) -> usize {
                self.n
            }
        }
        // }}}

        // {{{ Segtree 2D
        #[derive(Clone)]
        pub struct Segtree2D<M: Monoid> {
            n: usize,
            m: usize,
            pub trees: Vec<Segtree<M>>,
        }

        #[allow(unused)]
        impl<M: Monoid> Segtree2D<M> {
            pub fn new(n: usize, m: usize) -> Self {
                let mut trees = Vec::with_capacity(n * 2);
                for _ in 0..n * 2 {
                    trees.push(Segtree::<M>::new(m));
                }
                Segtree2D { n, m, trees }
            }

            fn __propagate(&mut self, mut i: usize, j: usize) {
                i >>= 1;
                while i > 0 {
                    let left = self.trees[i << 1].get(j);
                    let right = self.trees[i << 1 | 1].get(j);
                    self.trees[i].assign(j, M::operate(&left, &right));
                    i >>= 1;
                }
            }

            pub fn assign(&mut self, mut i: usize, j: usize, x: M::T) {
                debug_assert!(i < self.n);
                i += self.n;
                self.trees[i].assign(j, x);
                self.__propagate(i, j);
            }

            pub fn update(&mut self, mut i: usize, j: usize, x: M::T) {
                debug_assert!(i < self.n);
                i += self.n;
                self.trees[i].update(j, x);
                self.__propagate(i, j);
            }

            pub fn get(&mut self, i: usize, j: usize) -> M::T {
                self.trees[i + self.n].get(j)
            }

            pub fn fold<R>(&self, r_range: R, c_range: R) -> M::T
            where
                R: std::ops::RangeBounds<usize> + Clone,
            {
                let (rx, ry) = get_range(r_range, self.n);
                let mut rx = rx + self.n;
                let mut ry = ry + self.n;
                let mut vx = M::unit();
                let mut vy = M::unit();
                while rx < ry {
                    if rx & 1 != 0 {
                        vx = M::operate(&vx, &self.trees[rx].fold(c_range.clone()));
                        rx += 1;
                    }
                    if ry & 1 != 0 {
                        ry -= 1;
                        vy = M::operate(&self.trees[ry].fold(c_range.clone()), &vy);
                    }
                    rx >>= 1;
                    ry >>= 1;
                }
                M::operate(&vx, &vy)
            }
        }
        // }}}
    }
    // }}}

    // {{{ Graph
    #[allow(unused)]
    pub struct DenseGraph {
        pub n: usize,
        pub m: usize,
        pub visited: Vec<Vec<bool>>,
    }

    #[allow(unused)]
    impl DenseGraph {
        pub const DX: [isize; 8] = [-1, 0, 1, 0, 1, 1, -1, -1];
        pub const DY: [isize; 8] = [0, -1, 0, 1, 1, -1, -1, 1];
        pub const DC: [char; 8] = ['U', 'L', 'D', 'R', '↘', '↙', '↖', '↗'];

        pub fn new(n: usize, m: usize) -> Self {
            let mut visited = vec![vec![false; n + 2]; m + 2];
            // boundary init
            for i in 0..n + 2 {
                visited[i][0] = true;
                visited[i][m + 1] = true;
            }
            for j in 0..m + 2 {
                visited[0][j] = true;
                visited[n + 1][j] = true;
            }
            DenseGraph { n, m, visited }
        }

        pub fn next(&self, coord: (usize, usize), i: usize) -> (usize, usize) {
            (
                (coord.0 as isize + DenseGraph::DX[i]) as usize,
                (coord.1 as isize + DenseGraph::DY[i]) as usize,
            )
        }
    }
    // }}}
    // {{{ Disjoint Union Set
    #[allow(dead_code)]
    pub struct DSU {
        n: usize,
        size: Vec<usize>,
        link: Vec<usize>,
    }

    #[allow(unused)]
    impl DSU {
        pub fn new(n: usize) -> Self {
            DSU {
                n,
                size: vec![1usize; n],
                link: (0..n).collect::<Vec<usize>>(),
            }
        }

        pub fn find(&self, mut x: usize) -> usize {
            while x != self.link[x] {
                x = self.link[x];
            }
            x
        }

        pub fn same(&self, a: usize, b: usize) -> bool {
            self.find(a) == self.find(b)
        }

        pub fn merge(&mut self, mut a: usize, mut b: usize) -> bool {
            a = self.find(a);
            b = self.find(b);
            if a == b {
                return false;
            }

            let (a, b) = if self.size[a] < self.size[b] {
                (b, a)
            } else {
                (a, b)
            };
            self.size[a] += self.size[b];
            self.size[b] = 0;
            self.link[b] = a;
            true
        }
    }
    // }}}

    // {{{ chmin / chmax
    #[allow(unused)]
    pub fn chmax<T: Clone + PartialOrd>(x: &mut T, y: &T) -> bool {
        if *x < *y {
            x.clone_from(y);
            true
        } else {
            false
        }
    }
    #[allow(unused)]
    pub fn chmin<T: Clone + PartialOrd>(x: &mut T, y: &T) -> bool {
        if *x > *y {
            x.clone_from(y);
            true
        } else {
            false
        }
    }
    #[allow(unused)]
    #[macro_export]
    macro_rules! max {
        ($x:expr) => ($x);
        ($x:expr, $($tail:expr),+) => { std::cmp::max($x, max!($($tail),+)) }
    }
    #[allow(unused)]
    #[macro_export]
    macro_rules! min {
        ($x:expr) => ($x);
        ($x:expr, $($tail:expr),+) => { std::cmp::min($x, min!($($tail),+)) }
    }
    // }}}
    // {{{ Press
    #[allow(unused)]
    pub fn press<T: PartialEq>(a: Vec<T>) -> Vec<(T, usize)> {
        let mut ret: Vec<(T, usize)> = vec![];
        for x in a.into_iter() {
            if ret.is_empty() || ret.last().unwrap().0 != x {
                ret.push((x, 1));
            } else {
                ret.last_mut().unwrap().1 += 1;
            }
        }
        return ret;
    }
    // }}}
    // {{{ Next Permutation
    #[allow(unused)]
    pub fn next_permutation<T: Ord + PartialOrd>(nums: &mut Vec<T>) -> bool {
        use std::cmp::Ordering;
        let last_ascending = match nums.windows(2).rposition(|w| w[0] < w[1]) {
            Some(i) => i,
            None => {
                nums.reverse();
                return false;
            }
        };

        let swap_with = nums[last_ascending + 1..]
            .binary_search_by(|n| T::cmp(&nums[last_ascending], n).then(Ordering::Less))
            .unwrap_err();
        nums.swap(last_ascending, last_ascending + swap_with);
        nums[last_ascending + 1..].reverse();
        true
    }
    // }}}
    // {{{ kth
    pub trait Kth {
        fn kth(&self, k: usize) -> Option<usize>;
    }
    impl Kth for Segtree<Additive<usize>> {
        fn kth(&self, k: usize) -> Option<usize> {
            let mut l = 0;
            let mut r = self.len() - 1;
            let mut ret = None;
            while l <= r {
                let m = (l + r) >> 1;
                if self.fold(..=m) > k {
                    ret = Some(m);
                    if m == 0 {
                        break;
                    }
                    r = m - 1;
                } else {
                    l = m + 1;
                }
            }
            ret
        }
    }
    //}}}
    // {{{ Entry API
    pub trait CustomEntry<T: Ord> {
        fn dec_key(&mut self, key: T) -> bool;
    }

    impl<T: Ord> CustomEntry<T> for BTreeMap<T, usize> {
        fn dec_key(&mut self, key: T) -> bool {
            match self.entry(key) {
                btree_map::Entry::Occupied(mut entry) => {
                    if *entry.get() > 1 {
                        *entry.get_mut() -= 1;
                    } else {
                        entry.remove();
                    }
                    true
                }
                _ => false,
            }
        }
    }
    // }}}
}
// }}}

// <><><> More Lib Codes <><><>

crate::main!();
pub use iter_print::IterPrint;
pub use scanner::*;
// {{{ 内脏
// {{{ Main Macros
mod main_macros {
    #[doc = " - `prepare!();`: default (all input scanner (`sc!`, `sv!`) + buf print (`out!`, `dg!`))"]
    #[doc = " - `prepare!(?);`: interactive (line scanner (`scln!`) + buf print (`out!`, `dg!`))"]
    #[macro_export]
    macro_rules! prepare {
        (@output($dol:tt)) => {
            #[allow(unused_imports)]
            use std::io::Write as _;
            let __out=std::io::stdout();

            #[allow(unused_mut,unused_variables)]
            let mut __out=std::io::BufWriter::new(__out.lock());

            #[allow(unused_macros)]
            #[doc=" [`iter_print!`] for buffered stdout."]
            macro_rules! out {
                ($dol($dol t:tt)*) => {
                    $dol crate::iter_print!(__out, $dol($dol t)*)
                }
            }

            // error output
            #[cfg(debug_assertions)]
            #[allow(unused_macros)]
            #[doc=" [`iter_print!`] for buffered stderr. Do nothing in release mode."]
            macro_rules! dg {
                ($dol($dol t:tt)*) => {{
                    #[allow(unused_imports)]
                    use std::io::Write as _;
                    let __err = std::io::stderr();

                    #[allow(unused_mut, unused_variables)]
                    let mut __err = std::io::BufWriter::new(__err.lock());
                    $dol crate::iter_print!(__err, $dol($dol t)*);
                    let _ = __err.flush();
                }}
            }

            #[cfg(not(debug_assertions))]
            #[allow(unused_macros)]
            #[doc=" [`iter_print!`] for buffered stderr. Do nothing in release mode."]
            macro_rules! dg { ($dol($dol t:tt)*) => {} }
        };
        (@normal($dol:tt)) => {
            let __in_buf = read_stdin_all_unchecked();

            #[allow(unused_mut, unused_variables)]
            let mut __scanner = Scanner::new(&__in_buf);

            // two modes for scanning a value
            #[allow(unused_macros)]
            macro_rules! sc {
                ($dol($dol t:tt)*) => {
                    $dol crate::scan!(__scanner, $dol($dol t)*)
                }
            }

            #[allow(unused_macros)]
            macro_rules! sv {
                ($dol($dol t:tt)*) => {
                    $dol crate::scan_value!(__scanner, $dol($dol t)*)
                }
            }
        };
        (@interactive($dol:tt)) => {
            #[allow(unused_macros)]
            #[doc=" Scan a line, and previous line will be truncated in the next call."]
            macro_rules!scln{
                ($dol($dol t:tt)*) => {
                    let __in_buf = read_stdin_line();

                    #[allow(unused_mut, unused_variables)]
                    let mut __scanner = Scanner::new(&__in_buf);
                    $dol crate::scan!(__scanner, $dol($dol t)*)
                }
            }
        };
        () => {
            $crate::prepare!(@output($));
            $crate::prepare!(@normal($))
        };
        (?) => {
            $crate::prepare!(@output($));
            $crate::prepare!(@interactive($))
        };
    }

    // 3 modes for initializing the main class
    #[macro_export]
    macro_rules! main {
        () => {
            fn main() {
                solve();
            }
        };
        (avx2) => {
            fn main() {
                #[target_feature(enable = "avx2")]
                unsafe fn solve_avx2() {
                    solve();
                }
                unsafe { solve_avx2() }
            }
        };
        (large_stack) => {
            fn main() {
                const STACK_SIZE: usize = 512 * 1024 * 1024;
                ::std::thread::Builder::new()
                    .stack_size(STACK_SIZE)
                    .spawn(solve)
                    .unwrap()
                    .join()
                    .unwrap();
            }
        };
    }
}
// }}}
// {{{ IterPrint
mod iter_print {
    use std::{
        fmt::Display,
        io::{Error, Write},
    };

    pub trait IterPrint {
        fn iter_print<W, S>(self, writer: &mut W, sep: S, is_head: bool) -> Result<(), Error>
        where
            W: Write,
            S: Display;
    }

    macro_rules! iter_print_tuple_impl {
        (@impl$($A:ident$a:ident)?,$($B:ident$b:ident)*)=>{
            impl<$($A,)?$($B),*>IterPrint for($($A,)?$($B),*)where$($A:Display,)?$($B:Display),*{
                #[allow(unused_variables)]
                fn iter_print<W,S>(self,writer:&mut W,sep:S,is_head:bool)->Result<(),Error>
                where W:Write,S:Display{
                    let($($a,)?$($b,)*)=self;
                    $(if is_head { ::std::write!(writer,"{}",$a)?; } else { ::std::write!(writer,"{}{}",sep,$a)?; })?
                    $(::std::write!(writer,"{}{}",sep,$b)?;)*Ok(())
                }
            }
        };
        (@inc,,$C:ident$c:ident$($D:ident$d:ident)*)=>{
            iter_print_tuple_impl!(@impl,);
            iter_print_tuple_impl!(@inc$C$c,,$($D$d)*);
        };
        (@inc$A:ident$a:ident,$($B:ident$b:ident)*,$C:ident$c:ident$($D:ident$d:ident)*)=>{
            iter_print_tuple_impl!(@impl$A$a,$($B$b)*);
            iter_print_tuple_impl!(@inc$A$a,$($B$b)*$C$c,$($D$d)*);
        };
        (@inc$A:ident$a:ident,$($B:ident$b:ident)*,)=>{
            iter_print_tuple_impl!(@impl$A$a,$($B$b)*);
        };
        ($($t:tt)*)=>{
            iter_print_tuple_impl!(@inc,,$($t)*);
        };
    }
    iter_print_tuple_impl!(A a B b C c D d E e F f G g H h I i J j K k);

    #[doc = " Print expressions with a separator."]
    #[doc = " - `iter_print!(writer, args...)`"]
    #[doc = " - `@sep $expr`: set separator (default: `' '`)"]
    #[doc = " - `@ns`: alias for `@sep \"\"`"]
    #[doc = " - `@lf`: alias for `@sep '\\n'`"]
    #[doc = " - `@sp`: alias for `@sep ' '`"]
    #[doc = " - `@fmt ($lit, $($expr),*)`: print `format!($lit, $($expr),*)`"]
    #[doc = " - `@flush`: flush writer (auto insert `!`)"]
    #[doc = " - `@it $expr`: print iterator"]
    #[doc = " - `@it1 $expr`: print iterator as 1-indexed"]
    #[doc = " - `@cw ($char $expr)`: print iterator as `(elem as u8 + $char as u8) as char`"]
    #[doc = " - `@bw ($byte $expr)`: print iterator as `(elem as u8 + $byte) as char`"]
    #[doc = " - `@it2d $expr`: print 2d-iterator"]
    #[doc = " - `@tup $expr`: print tuple (need to import [`IterPrint`])"]
    #[doc = " - `@ittup $expr`: print iterative tuple (need to import [`IterPrint`])"]
    #[doc = " - `$expr`: print expr"]
    #[doc = " - `{ args... }`: scoped"]
    #[doc = " - `;`: print `'\\n'`"]
    #[doc = " - `!`: not print `'\\n'` at the end"]
    #[macro_export]
    macro_rules! iter_print {
        (@@fmt$writer:expr,$sep:expr,$is_head:expr,($lit:literal$(,$e:expr)*$(,)?))=>{
            if!$is_head{::std::write!($writer,"{}",$sep).expect("io error");}
            ::std::write!($writer,$lit,$($e),*).expect("io error");
        };
        (@@item$writer:expr,$sep:expr,$is_head:expr,$e:expr)=>{
            $crate::iter_print!(@@fmt$writer,$sep,$is_head,("{}",$e));
        };
        (@@line_feed$writer:expr$(,)?)=>{
            ::std::writeln!($writer).expect("io error");
        };
        (@@it$writer:expr,$sep:expr,$is_head:expr,$iter:expr)=>{{
            let mut iter=$iter.into_iter();
            if let Some(item)=iter.next(){
                $crate::iter_print!(@@item$writer,$sep,$is_head,item);
            }
            for item in iter{
                $crate::iter_print!(@@item$writer,$sep,false,item);
            }
        }};
        (@@it1$writer:expr,$sep:expr,$is_head:expr,$iter:expr)=>{{
            let mut iter=$iter.into_iter();
            if let Some(item)=iter.next(){
                $crate::iter_print!(@@item$writer,$sep,$is_head,item+1);
            }
            for item in iter{
                $crate::iter_print!(@@item$writer,$sep,false,item+1);
            }
        }};
        (@@cw$writer:expr,$sep:expr,$is_head:expr,($ch:literal$iter:expr))=>{{
            let mut iter=$iter.into_iter();
            let b=$ch as u8;
            if let Some(item)=iter.next(){
                $crate::iter_print!(@@item$writer,$sep,$is_head,(item as u8+b)as char);
            }
            for item in iter{
                $crate::iter_print!(@@item$writer,$sep,false,(item as u8+b)as char);
            }
        }};
        (@@bw$writer:expr,$sep:expr,$is_head:expr,($b:literal$iter:expr))=>{{
            let mut iter=$iter.into_iter();
            let b:u8=$b;
            if let Some(item)=iter.next(){
                $crate::iter_print!(@@item$writer,$sep,$is_head,(item as u8+b)as char);
            }
            for item in iter{
                $crate::iter_print!(@@item$writer,$sep,false,(item as u8+b)as char);
            }
        }};
        (@@it2d$writer:expr,$sep:expr,$is_head:expr,$iter:expr)=>{
            let mut iter=$iter.into_iter();
            if let Some(item)=iter.next(){
                $crate::iter_print!(@@it$writer,$sep,$is_head,item);
            }
            for item in iter{
                $crate::iter_print!(@@line_feed$writer);
                $crate::iter_print!(@@it$writer,$sep,true,item);
            }
        };
        (@@tup$writer:expr,$sep:expr,$is_head:expr,$tuple:expr)=>{
            IterPrint::iter_print($tuple,&mut$writer,$sep,$is_head).expect("io error");
        };
        (@@ittup$writer:expr,$sep:expr,$is_head:expr,$iter:expr)=>{
            let mut iter=$iter.into_iter();
            if let Some(item)=iter.next(){
                $crate::iter_print!(@@tup$writer,$sep,$is_head,item)
            }
            for item in iter{
                $crate::iter_print!(@@line_feed$writer);
                $crate::iter_print!(@@tup$writer,$sep,true,item);
            }
        };
        (@@assert_tag item)=>{};
        (@@assert_tag it)=>{};
        (@@assert_tag it1)=>{};
        (@@assert_tag it2d)=>{};
        (@@assert_tag tup)=>{};
        (@@assert_tag ittup)=>{};
        (@@assert_tag$tag:ident)=>{
            ::std::compile_error!(::std::concat!("invalid tag in `iter_print!`: `",std::stringify!($tag),"`"));
        };
        (@@inner$writer:expr,$sep:expr,$is_head:expr,@sep$e:expr,$($t:tt)*)=>{
            $crate::iter_print!(@@inner$writer,$e,$is_head,$($t)*);
        };
        (@@inner$writer:expr,$sep:expr,$is_head:expr,@ns$($t:tt)*)=>{
            $crate::iter_print!(@@inner$writer,"",$is_head,$($t)*);
        };
        (@@inner$writer:expr,$sep:expr,$is_head:expr,@lf$($t:tt)*)=>{
            $crate::iter_print!(@@inner$writer,'\n',$is_head,$($t)*);
        };
        (@@inner$writer:expr,$sep:expr,$is_head:expr,@sp$($t:tt)*)=>{
            $crate::iter_print!(@@inner$writer,' ',$is_head,$($t)*);
        };
        (@@inner$writer:expr,$sep:expr,$is_head:expr,@flush$($t:tt)*)=>{
            $writer.flush().expect("io error");
            $crate::iter_print!(@@inner$writer,$sep,$is_head,!$($t)*);
        };
        (@@inner$writer:expr,$sep:expr,$is_head:expr,@fmt$arg:tt$($t:tt)*)=>{
            $crate::iter_print!(@@fmt$writer,$sep,$is_head,$arg);
            $crate::iter_print!(@@inner$writer,$sep,$is_head,$($t)*);
        };
        (@@inner$writer:expr,$sep:expr,$is_head:expr,@cw$arg:tt$($t:tt)*)=>{
            $crate::iter_print!(@@cw$writer,$sep,$is_head,$arg);
            $crate::iter_print!(@@inner$writer,$sep,$is_head,$($t)*);
        };
        (@@inner$writer:expr,$sep:expr,$is_head:expr,@bw$arg:tt$($t:tt)*)=>{
            $crate::iter_print!(@@bw$writer,$sep,$is_head,$arg);
            $crate::iter_print!(@@inner$writer,$sep,$is_head,$($t)*);
        };
        (@@inner$writer:expr,$sep:expr,$is_head:expr,@$tag:ident$e:expr,$($t:tt)*)=>{
            $crate::iter_print!(@@assert_tag$tag);
            $crate::iter_print!(@@$tag$writer,$sep,$is_head,$e);
            $crate::iter_print!(@@inner$writer,$sep,false,$($t)*);
        };
        (@@inner$writer:expr,$sep:expr,$is_head:expr,@$tag:ident$e:expr;$($t:tt)*)=>{
            $crate::iter_print!(@@assert_tag$tag);
            $crate::iter_print!(@@$tag$writer,$sep,$is_head,$e);
            $crate::iter_print!(@@line_feed$writer);
            $crate::iter_print!(@@inner$writer,$sep,true,$($t)*);
        };
        (@@inner$writer:expr,$sep:expr,$is_head:expr,@$tag:ident$e:expr)=>{
            $crate::iter_print!(@@assert_tag$tag);
            $crate::iter_print!(@@$tag$writer,$sep,$is_head,$e);
            $crate::iter_print!(@@inner$writer,$sep,false,);
        };
        (@@inner$writer:expr,$sep:expr,$is_head:expr,@$tag:ident$($t:tt)*)=>{
            ::std::compile_error!(::std::concat!("invalid expr in `iter_print!`: `",std::stringify!($($t)*),"`"));
        };
        (@@inner$writer:expr,$sep:expr,$is_head:expr,,$($t:tt)*)=>{
            $crate::iter_print!(@@inner$writer,$sep,$is_head,$($t)*);
        };
        (@@inner$writer:expr,$sep:expr,$is_head:expr,;$($t:tt)*)=>{
            $crate::iter_print!(@@line_feed$writer);
            $crate::iter_print!(@@inner$writer,$sep,$is_head,$($t)*);
        };
        (@@inner$writer:expr,$sep:expr,$is_head:expr,!$(,)?)=>{};
        (@@inner$writer:expr,$sep:expr,$is_head:expr,!$($t:tt)*)=>{
            $crate::iter_print!(@@inner$writer,$sep,$is_head,$($t)*);
        };
        (@@inner$writer:expr,$sep:expr,$is_head:expr,)=>{
            $crate::iter_print!(@@line_feed$writer);
        };
        (@@inner$writer:expr,$sep:expr,$is_head:expr,{$($t:tt)*}$($rest:tt)*)=>{
            $crate::iter_print!(@@inner$writer,$sep,$is_head,$($t)*,!);
            $crate::iter_print!(@@inner$writer,$sep,$is_head,$($rest)*);
        };
        (@@inner$writer:expr,$sep:expr,$is_head:expr,$($t:tt)*)=>{
            $crate::iter_print!(@@inner$writer,$sep,$is_head,@item$($t)*);
        };
        ($writer:expr,$($t:tt)*)=>{{
            $crate::iter_print!(@@inner$writer,' ',true,$($t)*);
        }};
    }
}
// }}}
// {{{ Scanner
mod scanner {
    #[allow(unused_imports)]
    use std::io::Read;
    use std::{
        iter::{from_fn, repeat_with, FromIterator},
        marker::PhantomData,
    };

    // two ways to read stdin all at once
    pub fn read_stdin_all() -> String {
        use std::io::Read as _;
        let mut s = String::new();
        std::io::stdin().read_to_string(&mut s).expect("io error");
        s
    }

    pub fn read_stdin_all_unchecked() -> String {
        use std::io::Read as _;
        let mut buf = Vec::new();
        std::io::stdin().read_to_end(&mut buf).expect("io error");
        unsafe { String::from_utf8_unchecked(buf) }
    }

    // two ways to read from a reader instance
    pub fn read_all(mut reader: impl std::io::Read) -> String {
        let mut s = String::new();
        reader.read_to_string(&mut s).expect("io error");
        s
    }

    pub fn read_all_unchecked(mut reader: impl std::io::Read) -> String {
        let mut buf = Vec::new();
        reader.read_to_end(&mut buf).expect("io error");
        unsafe { String::from_utf8_unchecked(buf) }
    }

    // read one line at a time from stdin
    pub fn read_stdin_line() -> String {
        let mut s = String::new();
        std::io::stdin().read_line(&mut s).expect("io error");
        s
    }

    // scan with the original value, or scan with a modification
    pub trait IterScan: Sized {
        type Output;
        fn scan<'a, I: Iterator<Item = &'a str>>(iter: &mut I) -> Option<Self::Output>;
    }

    pub trait MarkedIterScan: Sized {
        type Output;
        fn mscan<'a, I: Iterator<Item = &'a str>>(self, iter: &mut I) -> Option<Self::Output>;
    }

    // the `Scanner` class
    #[derive(Clone, Debug)]
    pub struct Scanner<'a> {
        iter: std::str::SplitAsciiWhitespace<'a>,
    }

    impl<'a> Scanner<'a> {
        #[inline]
        pub fn new(s: &'a str) -> Self {
            let iter = s.split_ascii_whitespace();
            Self { iter }
        }
        #[inline]
        pub fn scan<T>(&mut self) -> <T as IterScan>::Output
        where
            T: IterScan,
        {
            <T as IterScan>::scan(&mut self.iter).expect("scan error")
        }
        // scan a type with a modification
        #[inline]
        pub fn mscan<T>(&mut self, marker: T) -> <T as MarkedIterScan>::Output
        where
            T: MarkedIterScan,
        {
            marker.mscan(&mut self.iter).expect("scan error")
        }
        // scan a vector
        #[inline]
        pub fn scan_vec<T>(&mut self, size: usize) -> Vec<<T as IterScan>::Output>
        where
            T: IterScan,
        {
            (0..size)
                .map(|_| <T as IterScan>::scan(&mut self.iter).expect("scan error"))
                .collect()
        }
        // scan a iterator
        #[inline]
        pub fn iter<'b, T>(&'b mut self) -> ScannerIter<'a, 'b, T>
        where
            T: IterScan,
        {
            ScannerIter {
                inner: self,
                _marker: std::marker::PhantomData,
            }
        }
    }

    macro_rules! iter_scan_impls {
        ($($t:ty)*) => {
            $(impl IterScan for$t{
                type Output = Self;
                #[inline]
                fn scan<'a,I:Iterator<Item=&'a str>>(iter:&mut I) -> Option<Self> {
                    iter.next()?.parse::<$t>().ok()
                }
            })*
        };
    }
    iter_scan_impls!(char u8 u16 u32 u64 usize i8 i16 i32 i64 isize f32 f64 u128 i128 String);

    macro_rules! iter_scan_tuple_impl {
        (@impl$($T:ident)*) => {
            impl <$($T:IterScan),*>IterScan for($($T,)*){
                type Output = ($(<$T as IterScan>::Output,)*);

                #[inline]
                fn scan<'a,It:Iterator<Item=&'a str>>(_iter:&mut It) -> Option<Self::Output> {
                    Some(($(<$T as IterScan>::scan(_iter)?,)*))
                }
            }
        };
        (@inner$($T:ident)*,) => {
            iter_scan_tuple_impl!(@impl$($T)*);
        };
        (@inner$($T:ident)*, $U:ident$($Rest:ident)*) => {
            iter_scan_tuple_impl!(@impl$($T)*);
            iter_scan_tuple_impl!(@inner$($T)*$U, $($Rest)*);
        };
        ($($T:ident)*) => {
            iter_scan_tuple_impl!(@inner, $($T)*);
        };
    }
    iter_scan_tuple_impl!(A B C D E F G H I J K);

    pub struct ScannerIter<'a, 'b, T> {
        inner: &'b mut Scanner<'a>,
        _marker: std::marker::PhantomData<fn() -> T>,
    }

    impl<'a, 'b, T> Iterator for ScannerIter<'a, 'b, T>
    where
        T: IterScan,
    {
        type Item = <T as IterScan>::Output;
        #[inline]
        fn next(&mut self) -> Option<Self::Item> {
            <T as IterScan>::scan(&mut self.inner.iter)
        }
    }

    #[doc = " scan and return the value"]
    #[doc = " - `scan_value!(scanner, ELEMENT)`"]
    #[doc = " ELEMENT :="]
    #[doc = " - `$ty`: IterScan"]
    #[doc = " - `@$expr`: MarkedIterScan"]
    #[doc = " - `[ELEMENT; $expr]`: vector"]
    #[doc = " - `[ELEMENT; const $expr]`: array"]
    #[doc = " - `[ELEMENT]`: iterator"]
    #[doc = " - `($(ELEMENT)*,)`: tuple"]
    #[macro_export]
    macro_rules! scan_value {
        (@repeat$scanner:expr, [$($t:tt)*]$($len:expr)?) => {
            ::std::iter::repeat_with(||$crate::scan_value!(@inner$scanner, []$($t)*))$(.take($len).collect::<Vec<_>>())?
        };
        (@array$scanner:expr, [$($t:tt)*]$len:expr) => {
            $crate::array![||$crate::scan_value!(@inner$scanner, []$($t)*);$len]
        };
        (@tuple$scanner:expr, [$([$($args:tt)*])*]) => {
            ($($($args)*,)*)
        };
        (@$tag:ident$scanner:expr, [[$($args:tt)*]]) => {
            $($args)*
        };
        (@$tag:ident$scanner:expr, [$($args:tt)*]@$e:expr) => {
            $crate::scan_value! (@$tag$scanner, [$($args)*[$scanner.mscan($e)]])
        };
        (@$tag:ident$scanner:expr, [$($args:tt)*]@$e:expr, $($t:tt)*) => {
            $crate::scan_value! (@$tag$scanner, [$($args)*[$scanner.mscan($e)]]$($t)*)
        };
        (@$tag:ident$scanner:expr, [$($args:tt)*]($($tuple:tt)*)$($t:tt)*) => {
            $crate::scan_value! (@$tag$scanner, [$($args)*[$crate::scan_value!(@tuple$scanner, []$($tuple)*)]]$($t)*)
        };
        (@$tag:ident$scanner:expr, [$($args:tt)*][@$e:expr;const$len:expr]$($t:tt)*) => {
            $crate::scan_value! (@$tag$scanner, [$($args)*[$crate::scan_value!(@array$scanner, [@$e]$len)]]$($t)*)
        };
        (@$tag:ident$scanner:expr, [$($args:tt)*][@$e:expr;$len:expr]$($t:tt)*) => {
            $crate::scan_value! (@$tag$scanner, [$($args)*[$crate::scan_value!(@repeat$scanner, [@$e]$len)]]$($t)*)
        };
        (@$tag:ident$scanner:expr, [$($args:tt)*][[$($tt:tt)*]; const$len:expr]$($t:tt)*) => {
            $crate::scan_value! (@$tag$scanner, [$($args)*[$crate::scan_value!(@array$scanner, [[$($tt)*]]$len)]]$($t)*)
        };
        (@$tag:ident$scanner:expr, [$($args:tt)*][[$($tt:tt)*]; $len:expr]$($t:tt)*) => {
            $crate::scan_value! (@$tag$scanner, [$($args)*[$crate::scan_value!(@repeat$scanner, [[$($tt)*]]$len)]]$($t)*)
        };
        (@$tag:ident$scanner:expr, [$($args:tt)*][($($tt:tt)*); const$len:expr]$($t:tt)*) => {
            $crate::scan_value! (@$tag$scanner, [$($args)*[$crate::scan_value!(@array$scanner, [($($tt)*)]$len)]]$($t)*)
        };
        (@$tag:ident$scanner:expr, [$($args:tt)*][($($tt:tt)*); $len:expr]$($t:tt)*) => {
            $crate::scan_value! (@$tag$scanner, [$($args)*[$crate::scan_value!(@repeat$scanner, [($($tt)*)]$len)]]$($t)*)
        };
        (@$tag:ident$scanner:expr, [$($args:tt)*][$ty:ty; const$len:expr]$($t:tt)*) => {
            $crate::scan_value! (@$tag$scanner, [$($args)*[$crate::scan_value!(@array$scanner, [$ty]$len)]]$($t)*)
        };
        (@$tag:ident$scanner:expr, [$($args:tt)*][$ty:ty; $len:expr]$($t:tt)*) => {
            $crate::scan_value! (@$tag$scanner, [$($args)*[$crate::scan_value! (@repeat$scanner, [$ty]$len)]]$($t)*)
        };
        (@$tag:ident$scanner:expr, [$($args:tt)*][$($tt:tt)*]$($t:tt)*) => {
            $crate::scan_value! (@$tag$scanner, [$($args)*[$crate::scan_value! (@repeat$scanner, [$($tt)*])]]$($t)*)
        };
        (@$tag:ident$scanner:expr, [$($args:tt)*]$ty:ty) => {
            $crate::scan_value! (@$tag$scanner, [$($args)*[$scanner.scan::<$ty>()]])
        };
        (@$tag:ident$scanner:expr, [$($args:tt)*]$ty:ty,$($t:tt)*) => {
            $crate::scan_value! (@$tag$scanner, [$($args)*[$scanner.scan::<$ty>()]]$($t)*)
        };
        (@$tag:ident$scanner:expr, [$($args:tt)*],$($t:tt)*) => {
            $crate::scan_value! (@$tag$scanner, [$($args)*]$($t)*)
        };
        (@$tag:ident$scanner:expr, [$($args:tt)*]) => {
            ::std::compile_error! (::std::stringify!($($args)*))
        };
        ($scanner:expr,$($t:tt)*) => {
            $crate::scan_value! (@inner$scanner, []$($t)*)
        }
    }

    #[doc = " scan and bind values"]
    #[doc = " - `scan!(scanner, $($pat $(: ELEMENT)?),*)`"]
    #[macro_export]
    macro_rules! scan {
        (@assert$p:pat) => {};
        (@assert$($p:tt)*) => {
            ::std::compile_error!(::std::concat!("expected pattern, found `", ::std::stringify!($($p)*), "`"));
        };

        // inner: pattern part
        (@pat$scanner:expr, [][]) => {};
        (@pat$scanner:expr, [][], $($t:tt)*) => {
            $crate::scan! (@pat$scanner, [][]$($t)*)
        };
        (@pat$scanner:expr, [$($p:tt)*][]$x:ident$($t:tt)*) => {
            $crate::scan! (@pat$scanner, [$($p)*$x][]$($t)*)
        };
        (@pat$scanner:expr, [$($p:tt)*][]::$($t:tt)*) => {
            $crate::scan! (@pat$scanner, [$($p)*::][]$($t)*)
        };
        (@pat$scanner:expr, [$($p:tt)*][]&$($t:tt)*) => {
            $crate::scan! (@pat$scanner, [$($p)*&][]$($t)*)
        };
        (@pat$scanner:expr, [$($p:tt)*][]($($x:tt)*)$($t:tt)*) => {
            $crate::scan! (@pat$scanner, [$($p)*($($x)*)][]$($t)*)
        };
        (@pat$scanner:expr, [$($p:tt)*][][$($x:tt)*]$($t:tt)*) => {
            $crate::scan! (@pat$scanner, [$($p)*[$($x)*]][]$($t)*)
        };
        (@pat$scanner:expr, [$($p:tt)*][]{$($x:tt)*}$($t:tt)*) => {
            $crate::scan! (@pat$scanner, [$($p)*{$($x)*}][]$($t)*)
        };
        (@pat$scanner:expr, [$($p:tt)*][]:$($t:tt)*) => {
            $crate::scan! (@ty$scanner, [$($p)*][]$($t)*)
        };
        (@pat$scanner:expr, [$($p:tt)*][]$($t:tt)*) => {
            $crate::scan! (@let$scanner, [$($p)*][usize]$($t)*)
        };

        // inner: ty part
        (@ty$scanner:expr, [$($p:tt)*][$($tt:tt)*]@$e:expr) => {
            $crate::scan! (@let$scanner, [$($p)*][$($tt)*@$e])
        };
        (@ty$scanner:expr, [$($p:tt)*][$($tt:tt)*]@$e:expr,$($t:tt)*) => {
            $crate::scan! (@let$scanner, [$($p)*][$($tt)*@$e],$($t)*)
        };
        (@ty$scanner:expr, [$($p:tt)*][$($tt:tt)*]($($x:tt)*)$($t:tt)*) => {
            $crate::scan! (@let$scanner, [$($p)*][$($tt)*($($x)*)]$($t)*)
        };
        (@ty$scanner:expr, [$($p:tt)*][$($tt:tt)*][$($x:tt)*]$($t:tt)*) => {
            $crate::scan! (@let$scanner, [$($p)*][$($tt)*[$($x)*]]$($t)*)
        };
        (@ty$scanner:expr, [$($p:tt)*][$($tt:tt)*]$ty:ty) => {
            $crate::scan! (@let$scanner, [$($p)*][$($tt)*$ty])
        };
        (@ty$scanner:expr, [$($p:tt)*][$($tt:tt)*]$ty:ty,$($t:tt)*) => {
            $crate::scan! (@let$scanner, [$($p)*][$($tt)*$ty],$($t)*)
        };

        // inner: let part
        (@let$scanner:expr, [$($p:tt)*][$($tt:tt)*]$($t:tt)*) => {
            $crate::scan! { @assert$($p)* }
            let$($p)* = $crate::scan_value! ($scanner, $($tt)*);
            $crate::scan! (@pat$scanner, [][]$($t)*)
        };

        ($scanner:expr, $($t:tt)*) => {
            $crate::scan! (@pat$scanner, [][]$($t)*)
        }
    }

    #[derive(Debug, Copy, Clone)]
    pub enum Usize1 {}

    impl IterScan for Usize1 {
        type Output = usize;
        #[inline]
        fn scan<'a, I: Iterator<Item = &'a str>>(iter: &mut I) -> Option<Self::Output> {
            <usize as IterScan>::scan(iter)?.checked_sub(1)
        }
    }

    #[derive(Debug, Copy, Clone)]
    pub struct CharWithBase(pub char);

    impl MarkedIterScan for CharWithBase {
        type Output = usize;
        #[inline]
        fn mscan<'a, I: Iterator<Item = &'a str>>(self, iter: &mut I) -> Option<Self::Output> {
            Some((<char as IterScan>::scan(iter)? as u8 - self.0 as u8) as usize)
        }
    }

    #[derive(Debug, Copy, Clone)]
    pub enum Chars {}

    impl IterScan for Chars {
        type Output = Vec<char>;
        #[inline]
        fn scan<'a, I: Iterator<Item = &'a str>>(iter: &mut I) -> Option<Self::Output> {
            Some(iter.next()?.chars().collect())
        }
    }

    #[derive(Debug, Copy, Clone)]
    pub struct CharsWithBase(pub char);

    impl MarkedIterScan for CharsWithBase {
        type Output = Vec<usize>;
        #[inline]
        fn mscan<'a, I: Iterator<Item = &'a str>>(self, iter: &mut I) -> Option<Self::Output> {
            Some(
                iter.next()?
                    .chars()
                    .map(|c| (c as u8 - self.0 as u8) as usize)
                    .collect(),
            )
        }
    }

    #[derive(Debug, Copy, Clone)]
    pub enum Byte1 {}

    impl IterScan for Byte1 {
        type Output = u8;
        #[inline]
        fn scan<'a, I: Iterator<Item = &'a str>>(iter: &mut I) -> Option<Self::Output> {
            let bytes = iter.next()?.as_bytes();
            assert_eq!(bytes.len(), 1);
            Some(bytes[0])
        }
    }

    #[derive(Debug, Copy, Clone)]
    pub struct ByteWithBase(pub u8);

    impl MarkedIterScan for ByteWithBase {
        type Output = usize;
        #[inline]
        fn mscan<'a, I: Iterator<Item = &'a str>>(self, iter: &mut I) -> Option<Self::Output> {
            Some((<char as IterScan>::scan(iter)? as u8 - self.0) as usize)
        }
    }

    #[derive(Debug, Copy, Clone)]
    pub enum Bytes {}

    impl IterScan for Bytes {
        type Output = Vec<u8>;
        #[inline]
        fn scan<'a, I: Iterator<Item = &'a str>>(iter: &mut I) -> Option<Self::Output> {
            Some(iter.next()?.bytes().collect())
        }
    }

    #[derive(Debug, Copy, Clone)]
    pub struct BytesWithBase(pub u8);

    impl MarkedIterScan for BytesWithBase {
        type Output = Vec<usize>;
        #[inline]
        fn mscan<'a, I: Iterator<Item = &'a str>>(self, iter: &mut I) -> Option<Self::Output> {
            Some(
                iter.next()?
                    .bytes()
                    .map(|c| (c - self.0) as usize)
                    .collect(),
            )
        }
    }

    // TODO
    #[derive(Debug, Copy, Clone)]
    pub struct Collect<T, B = Vec<<T as IterScan>::Output>>
    where
        T: IterScan,
        B: FromIterator<<T as IterScan>::Output>,
    {
        size: usize,
        _marker: PhantomData<fn() -> (T, B)>,
    }

    impl<T, B> Collect<T, B>
    where
        T: IterScan,
        B: FromIterator<<T as IterScan>::Output>,
    {
        pub fn new(size: usize) -> Self {
            Self {
                size,
                _marker: PhantomData,
            }
        }
    }

    impl<T, B> MarkedIterScan for Collect<T, B>
    where
        T: IterScan,
        B: FromIterator<<T as IterScan>::Output>,
    {
        type Output = B;
        #[inline]
        fn mscan<'a, I: Iterator<Item = &'a str>>(self, iter: &mut I) -> Option<Self::Output> {
            repeat_with(|| <T as IterScan>::scan(iter))
                .take(self.size)
                .collect()
        }
    }

    // TODO
    #[derive(Debug, Copy, Clone)]
    pub struct SizedCollect<T, B = Vec<<T as IterScan>::Output>>
    where
        T: IterScan,
        B: FromIterator<<T as IterScan>::Output>,
    {
        _marker: PhantomData<fn() -> (T, B)>,
    }

    impl<T, B> IterScan for SizedCollect<T, B>
    where
        T: IterScan,
        B: FromIterator<<T as IterScan>::Output>,
    {
        type Output = B;
        #[inline]
        fn scan<'a, I: Iterator<Item = &'a str>>(iter: &mut I) -> Option<Self::Output> {
            let size = usize::scan(iter)?;
            repeat_with(|| <T as IterScan>::scan(iter))
                .take(size)
                .collect()
        }
    }

    // TODO
    #[derive(Debug, Copy, Clone)]
    pub struct Splitted<T, P>
    where
        T: IterScan,
    {
        pat: P,
        _marker: PhantomData<fn() -> T>,
    }

    impl<T, P> Splitted<T, P>
    where
        T: IterScan,
    {
        pub fn new(pat: P) -> Self {
            Self {
                pat,
                _marker: PhantomData,
            }
        }
    }

    impl<T> MarkedIterScan for Splitted<T, char>
    where
        T: IterScan,
    {
        type Output = Vec<<T as IterScan>::Output>;
        fn mscan<'a, I: Iterator<Item = &'a str>>(self, iter: &mut I) -> Option<Self::Output> {
            let mut iter = iter.next()?.split(self.pat);
            Some(from_fn(|| <T as IterScan>::scan(&mut iter)).collect())
        }
    }

    impl<T> MarkedIterScan for Splitted<T, &str>
    where
        T: IterScan,
    {
        type Output = Vec<<T as IterScan>::Output>;
        fn mscan<'a, I: Iterator<Item = &'a str>>(self, iter: &mut I) -> Option<Self::Output> {
            let mut iter = iter.next()?.split(self.pat);
            Some(from_fn(|| <T as IterScan>::scan(&mut iter)).collect())
        }
    }

    impl<T, F> MarkedIterScan for F
    where
        F: Fn(&str) -> Option<T>,
    {
        type Output = T;
        fn mscan<'a, I: Iterator<Item = &'a str>>(self, iter: &mut I) -> Option<Self::Output> {
            self(iter.next()?)
        }
    }
}
// }}}
// }}}