Submission #39921260

---

Source Code Expand

// -*- coding:utf-8-unix -*-
// rustup doc --std --toolchain 1.42.0
#![allow(unused_imports)]

pub fn solve() {
    // Initialize.
    use fastproconio::*;
    #[rustfmt::skip] #[cfg(tcheck)] let tins = std::time::Instant::now();
    #[rustfmt::skip] #[cfg(tcheck)] let mut durs = Vec::with_capacity(16);
    let stdin = std::io::stdin();
    let mut source = ProconIBufIter::new(stdin.lock());
    #[rustfmt::skip] #[allow(unused_macros)] macro_rules! finput {($($r:tt)*)=>{finput_inner!{source,$($r)*}};}
    #[rustfmt::skip] #[allow(unused_macros)] macro_rules! fread {($t:tt)=>{{fread_value!(source,$t)}};}
    let mut obuf = ProconWriteBuffer::with_capacity(1 << 26);
    let mut out = std::io::stdout();
    //let mut out = std::io::BufWriter::with_capacity(out.lock(), 1 << 26);
    //let err = std::io::stderr();
    //let mut err = std::io::BufWriter::with_capacity(err.lock(), 1 << 26);
    #[rustfmt::skip] #[cfg(tcheck)] durs.push((tins.elapsed(), String::from("initialize")));

    // Input. (Only some or no input if you want to input in parallel with the main process.)
    finput! {
        t: usize,
    }
    #[rustfmt::skip] #[cfg(tcheck)] durs.push((tins.elapsed(), String::from("input")));

    // Main Process, Output.

    let mut dfs_queue = VecDeque::<(u16, u16)>::with_capacity(65536);
    'testcases: /* ' */ for _ in 0..t {
        dfs_queue.clear();
        finput! {
            n: usize, m: usize,
            c: [byte; n],
        }
        let n1_u16 = n as u16 - 1;
        let mut arrive_bitset = vec![0u32; n * n / 32 + 1];
        invariant!(((n1_u16 / 32) as usize) < arrive_bitset.len());
        arrive_bitset[(n1_u16 / 32) as usize] |= 1 << (n1_u16 % 32);
        let mut edges = (0..(n * 2)).map(|_| smallvec::SmallVec::<[u16; 4]>::new()).collect::<Vec<_>>();
        //let mut edges = (0..(n * 2)).map(|_| Vec::new()).collect::<Vec<_>>();
        for _ in 0..m {
            finput! {
                u: u16_1, v: u16_1,
            }
            invariant!((u as usize) < c.len());
            invariant!((v as usize) < c.len());
            let uidx = u as usize * 2 + if c[v as usize] == b'1' { 1 } else { 0 };
            let vidx = v as usize * 2 + if c[u as usize] == b'1' { 1 } else { 0 };
            invariant!(uidx < edges.len());
            invariant!(vidx < edges.len());
            edges[uidx].push(v);
            edges[vidx].push(u);
        }
        invariant!(n - 1 < c.len());
        if c[0] == c[n - 1] {
            obuf.bytes(b"-1\n");
            continue;
        }
        dfs_queue.push_back((0, n1_u16));
        for step in 0u32.. {
            if dfs_queue.is_empty() {
                break;
            }
            let l = dfs_queue.len();
            for _ in 0..l {
                let (s, t) = dfs_queue.pop_front().unwrap();
                if s == n1_u16 && t == 0 {
                    obuf.uint(step);
                    obuf.lf();
                    continue 'testcases; /* ' */
                }
                invariant!(s as usize * 2 + 0 < edges.len());
                invariant!(s as usize * 2 + 1 < edges.len());
                invariant!(t as usize * 2 + 0 < edges.len());
                invariant!(t as usize * 2 + 1 < edges.len());
                let es0 = &edges[s as usize * 2 + 0];
                let es1 = &edges[s as usize * 2 + 1];
                let et0 = &edges[t as usize * 2 + 0];
                let et1 = &edges[t as usize * 2 + 1];
                for &s_next in es0.iter() {
                    let arrive_cindex = (s_next as usize) * n;
                    for &t_next in et1.iter() {
                        let bidx = arrive_cindex + t_next as usize;
                        invariant!(bidx / 32 < arrive_bitset.len());
                        if ((arrive_bitset[bidx / 32] >> (bidx % 32)) & 1) == 0 {
                            arrive_bitset[bidx / 32] |= 1 << (bidx % 32);
                            dfs_queue.push_back((s_next, t_next));
                        }
                    }
                }
                for &s_next in es1.iter() {
                    let arrive_cindex = (s_next as usize) * n;
                    for &t_next in et0.iter() {
                        let bidx = arrive_cindex + t_next as usize;
                        invariant!(bidx / 32 < arrive_bitset.len());
                        if ((arrive_bitset[bidx / 32] >> (bidx % 32)) & 1) == 0 {
                            arrive_bitset[bidx / 32] |= 1 << (bidx % 32);
                            dfs_queue.push_back((s_next, t_next));
                        }
                    }
                }
            }
        }
        obuf.bytes(b"-1\n");
    }
    obuf.write_all(&mut out);
    //std::io::Write::flush(&mut out).ok();
    #[rustfmt::skip] #[cfg(tcheck)] durs.push((tins.elapsed(), String::from("output")));

    // Execution Time.
    #[rustfmt::skip] #[cfg(tcheck)] for (dur, s) in durs.iter() { eprintln!("{:.6} {}", dur.as_secs_f64(), s); };
}

pub fn main() {
    const USE_THREAD: bool = true;
    if USE_THREAD {
        // In order to avoid potential stack overflow, spawn a new thread.
        let stack_size = 134_217_728; // 128 MB
        let thd = std::thread::Builder::new().stack_size(stack_size);
        thd.spawn(|| solve()).unwrap().join().unwrap();
    } else {
        solve()
    }
}

#[allow(unused_macros)]
#[macro_export]
macro_rules! invariant {
    ($expr: expr) => {
        debug_assert!($expr);
        if !($expr) {
            unsafe { core::hint::unreachable_unchecked() };
        }
    };
}

/*
use bitset_fixed::BitSet;
use itertools::*;
use num::integer::*;
use petgraph::algo::*;
use petgraph::graph::{DiGraph, Graph, NodeIndex, UnGraph};
use petgraph::unionfind::UnionFind;
use petgraph::visit::{
    Bfs, Dfs, EdgeRef, IntoEdges, NodeCount, NodeIndexable, VisitMap, Visitable,
};
//use proconio::{input, marker::{Bytes, Chars, Isize1, Usize1}, source::{auto::AutoSource, line::LineSource, once::OnceSource}};
use rand::{
    distributions::WeightedIndex,
    prelude::{thread_rng, Distribution},
    seq::SliceRandom,
    Rng,
};
use regex::Regex;
use rustc_hash::FxHasher;
use std::hash::BuildHasherDefault;
use superslice::Ext;
*/
use std::collections::*;
use std::io::{stderr, stdin, stdout, BufRead, BufReader, BufWriter, Read, Write};

/// chmax, chmin sugar syntax
trait Change {
    fn chmax(&mut self, x: Self);
    fn chmin(&mut self, x: Self);
}
impl<T: PartialOrd> Change for T {
    fn chmax(&mut self, x: T) {
        if *self < x {
            *self = x;
        }
    }
    fn chmin(&mut self, x: T) {
        if *self > x {
            *self = x;
        }
    }
}
pub mod fastproconio {
    use std::convert::TryInto;

    /// input macros based on tanakh's input macro / proconio-rs.
    /// tanakh's input macro: <https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8>
    /// proconio-rs: <https://docs.rs/proconio/0.3.8/proconio/>
    /// ProconIBufIter receive `std::io::BufRead` trait. (`std::io::StdinLock`, `std::io::BufReader`, `&[u8]`, etc.)
    #[macro_export]
    macro_rules! finput_inner {
        ($source:expr) => {};
        ($source:expr, ) => {};
        ($source:expr, mut $var:ident : $t:tt $($r:tt)*) => {
            let mut $var = fread_value!($source, $t);
            finput_inner!{$source $($r)*}
        };
        ($source:expr, $var:ident : $t:tt $($r:tt)*) => {
            let $var = fread_value!($source, $t);
            finput_inner!{$source $($r)*}
        };
    }
    #[macro_export]
    macro_rules! fread_value {
        ($source:expr, ( $($t:tt),* )) => { ( $(fread_value!($source, $t)),* ) };
        ($source:expr, [ $t:tt ; $len:expr ]) => { (0..$len).map(|_| fread_value!($source, $t)).collect::<Vec<_>>() };
        ($source:expr, u128) => { $source.next_wordtoken().as_slice().parse_u128_raw() };
        ($source:expr, usize) => { $source.next_wordtoken().as_slice().parse_u64_raw() as usize };
        ($source:expr, usize1) => { $source.next_wordtoken().as_slice().parse_u64_raw() as usize - 1 };
        ($source:expr, u64) => { $source.next_wordtoken().as_slice().parse_u64_raw() };
        ($source:expr, u64_1) => { $source.next_wordtoken().as_slice().parse_u64_raw() - 1 };
        ($source:expr, u32) => { $source.next_wordtoken().as_slice().parse_u32_raw() };
        ($source:expr, u32_1) => { $source.next_wordtoken().as_slice().parse_u32_raw() - 1 };
        ($source:expr, u16) => { $source.next_wordtoken().as_slice().parse_u16_raw() };
        ($source:expr, u16_1) => { $source.next_wordtoken().as_slice().parse_u16_raw() - 1 };
        ($source:expr, u8) => { $source.next_wordtoken().as_slice().parse_u8_raw() };
        ($source:expr, i128) => { $source.next_wordtoken().as_slice().parse_i128_raw() };
        ($source:expr, isize) => { $source.next_wordtoken().as_slice().parse_i64_raw() as isize };
        ($source:expr, i64) => { $source.next_wordtoken().as_slice().parse_i64_raw() };
        ($source:expr, i32) => { $source.next_wordtoken().as_slice().parse_i32_raw() };
        ($source:expr, i16) => { $source.next_wordtoken().as_slice().parse_i16_raw() };
        ($source:expr, i8) => { $source.next_wordtoken().as_slice().parse_i8_raw() };
        ($source:expr, byte) => { $source.get_ascii_byte() };
        ($source:expr, Bytes) => {{ $source.next_wordtoken().as_vec() }};
        ($source:expr, BytesToken) => {{ $source.next_wordtoken() }};
        ($source:expr, String) => {unsafe { $source.next_wordtoken().as_string_unchecked() }};
        ($source:expr, LineBytes) => {{ $source.next_linetoken().as_vec() }};
        ($source:expr, LineBytesToken) => {{ $source.next_linetoken() }};
        ($source:expr, LineString) => {unsafe { $source.next_linetoken().as_string_unchecked() }};
        ($source:expr, $t:ty) => {{ let mut v = vec![];$source.get_utf8_bytes(&mut v);unsafe { std::string::String::from_utf8_unchecked(v.as_slice()) }.parse::<$t>().expect("Parse error") }};
    }
    unsafe fn ptr_offset_u8(dist: *const u8, origin: *const u8) -> usize {
        // Rust 1.47.0 or later, `dist.offset_from(origin) as usize`
        // <https://doc.rust-lang.org/std/primitive.pointer.html#method.offset_from>
        dist as usize - origin as usize
    }
    #[derive(Clone, Debug)]
    pub enum Token<'a> {
        Slice(&'a [u8]),
        Bytes(Vec<u8>),
    }
    impl Token<'_> /* ' */ {
        pub fn as_slice(&self) -> &[u8] {
            match self {
                Self::Slice(s) => s,
                Self::Bytes(v) => v.as_slice(),
            }
        }
        pub fn as_vec(self) -> Vec<u8> {
            match self {
                Self::Slice(s) => s.to_vec(),
                Self::Bytes(v) => v,
            }
        }
        pub fn as_string(self) -> Result<String, std::string::FromUtf8Error> {
            String::from_utf8(self.as_vec())
        }
        pub unsafe fn as_string_unchecked(self) -> String {
            String::from_utf8_unchecked(self.as_vec())
        }
    }

    /// Interaction with `std::io::BufRead` Trait, Implementation of `Iterator<Item = u8>`
    pub struct ProconIBufIter<R: std::io::BufRead> {
        inner: R,
        raw: *const u8,
        ptr: *const u8,
        end: *const u8,
        len: usize,
        balign: *const u8,
        wmask: Vec<u64>,
    }
    impl<R: std::io::BufRead> ProconIBufIter<R> {
        pub fn new(inner: R) -> Self {
            const EMPTY_U8_SLICE: &'static /* ' */ [u8] = b"";
            Self {
                inner,
                raw: EMPTY_U8_SLICE.as_ptr(),
                ptr: EMPTY_U8_SLICE.as_ptr(),
                end: EMPTY_U8_SLICE.as_ptr(),
                len: 0,
                balign: EMPTY_U8_SLICE.as_ptr(),
                wmask: vec![0u64; 200],
            }
        }
    }
    impl<R: std::io::BufRead> ProconIBufIter<R> {
        pub fn buf_empty(&self) -> bool {
            self.ptr == self.end
        }
        #[allow(clippy::missing_safety_doc)]
        #[cold]
        unsafe fn inner_read(&mut self) -> bool {
            debug_assert_eq!(self.ptr, self.end);
            self.inner.consume(ptr_offset_u8(self.ptr, self.raw));
            if let Ok(s) = self.inner.fill_buf() {
                self.raw = s.as_ptr();
                self.ptr = s.as_ptr();
                self.end = s.as_ptr().add(s.len());
                self.len = s.len();
                self.balign = (self.raw as usize & !0x3f) as *const u8;
                let alignlen = (((self.end as usize) + 0x3f) & (!0x3f)) - self.balign as usize;
                let wmasklen = (alignlen + 63) / 64;
                #[cfg(target_arch = "x86_64")]
                {
                    #[target_feature(enable = "avx2")]
                    unsafe fn genmask_avx2(asl: &[u8], bsl: &mut [u64]) {
                        use std::arch::x86_64::*;
                        let diff = _mm256_set1_epi8(-0x21);
                        for (a, b) in asl.chunks_exact(64).zip(bsl.iter_mut()) {
                            let s0 = _mm256_load_si256(std::mem::transmute(a.as_ptr().add(0)));
                            let s1 = _mm256_load_si256(std::mem::transmute(a.as_ptr().add(32)));
                            let a0 = _mm256_add_epi8(s0, diff);
                            let a1 = _mm256_add_epi8(s1, diff);
                            let m0 = _mm256_movemask_epi8(_mm256_andnot_si256(s0, a0)) as u32;
                            let m1 = _mm256_movemask_epi8(_mm256_andnot_si256(s1, a1)) as u32;
                            *b = ((m1 as u64) << 32) | (m0 as u64);
                        }
                    }
                    unsafe fn genmask_sse2(asl: &[u8], bsl: &mut [u64]) {
                        use std::arch::x86_64::*;
                        let diff = _mm_set1_epi8(-0x21);
                        for (a, b) in asl.chunks_exact(64).zip(bsl.iter_mut()) {
                            let s0 = _mm_load_si128(std::mem::transmute(a.as_ptr().add(0)));
                            let s1 = _mm_load_si128(std::mem::transmute(a.as_ptr().add(16)));
                            let s2 = _mm_load_si128(std::mem::transmute(a.as_ptr().add(32)));
                            let s3 = _mm_load_si128(std::mem::transmute(a.as_ptr().add(48)));
                            let a0 = _mm_add_epi8(s0, diff);
                            let a1 = _mm_add_epi8(s1, diff);
                            let a2 = _mm_add_epi8(s2, diff);
                            let a3 = _mm_add_epi8(s3, diff);
                            let m0 = _mm_movemask_epi8(_mm_andnot_si128(s0, a0)) as u16;
                            let m1 = _mm_movemask_epi8(_mm_andnot_si128(s1, a1)) as u16;
                            let m2 = _mm_movemask_epi8(_mm_andnot_si128(s2, a2)) as u16;
                            let m3 = _mm_movemask_epi8(_mm_andnot_si128(s3, a3)) as u16;
                            *b = ((m3 as u64) << 48)
                                | ((m2 as u64) << 32)
                                | ((m1 as u64) << 16)
                                | (m0 as u64);
                        }
                    }
                    if self.wmask.len() <= wmasklen {
                        self.wmask
                            .extend(std::iter::repeat(0).take(wmasklen + 1 - self.wmask.len()));
                    }
                    let asl = std::slice::from_raw_parts(self.balign, wmasklen * 64);
                    if is_x86_feature_detected!("avx2") {
                        genmask_avx2(asl, &mut self.wmask);
                    } else {
                        genmask_sse2(asl, &mut self.wmask);
                    }
                };
                self.len != 0
            } else {
                self.raw = self.ptr;
                self.len = self.end as usize - self.ptr as usize;
                false
            }
        }
        #[allow(clippy::missing_safety_doc)]
        unsafe fn next_unchecked(&mut self) -> u8 {
            let p = self.ptr;
            self.ptr = p.add(1);
            *p
        }
        /// skip unmatch bytes
        pub fn skipuntil_bytes_fn<F: FnMut(u8) -> bool>(&mut self, f: &mut F) -> bool {
            loop {
                let mut ptr = self.ptr;
                while ptr != self.end {
                    if f(unsafe { *ptr }) {
                        self.ptr = ptr;
                        return true;
                    }
                    unsafe {
                        ptr = ptr.add(1);
                    }
                }
                self.ptr = ptr;
                if unsafe { !self.inner_read() } {
                    return false;
                }
            }
        }
        pub fn get_ascii_bytes(&mut self, vec: &mut Vec<u8>) {
            if !self.skipuntil_bytes_fn(&mut |c: u8| c > b' ') {
                return;
            }
            #[cfg(target_arch = "x86_64")]
            unsafe {
                let ptr = self.ptr;
                let pdiff = (self.ptr as usize) - (self.balign as usize) + 1;
                let (p64q, p64r) = (pdiff / 64, pdiff % 64);
                let mut w = self.wmask.as_ptr().add(p64q);
                let wmask = (*w) & ((!0u64) << p64r);
                let mut p = self.balign.add(p64q * 64);
                if wmask != 0 {
                    p = p.add(wmask.trailing_zeros() as usize);
                    if p < self.end {
                        self.ptr = p.add(1);
                        vec.extend_from_slice(std::slice::from_raw_parts(
                            ptr,
                            p as usize - ptr as usize,
                        ));
                        return;
                    }
                }
                p = p.add(64);
                w = w.add(1);
                let end64 = self.end.sub(64);
                while p < end64 {
                    let wmask = *w;
                    if wmask != 0 {
                        let tlz = wmask.trailing_zeros();
                        let pp = p.add(tlz as usize);
                        self.ptr = pp.add(1);
                        vec.extend_from_slice(std::slice::from_raw_parts(
                            ptr,
                            pp as usize - ptr as usize,
                        ));
                        return;
                    }
                    p = p.add(64);
                    w = w.add(1);
                }
                if p < self.end {
                    let wmask = *w;
                    if wmask != 0 {
                        let tlz = wmask.trailing_zeros();
                        let pp = p.add(tlz as usize);
                        if pp < self.end {
                            self.ptr = pp.add(1);
                            vec.extend_from_slice(std::slice::from_raw_parts(
                                ptr,
                                pp as usize - ptr as usize,
                            ));
                            return;
                        }
                    }
                }
                vec.extend_from_slice(std::slice::from_raw_parts(ptr, self.end as usize - ptr as usize));
                loop {
                    self.ptr = self.end;
                    if !self.inner_read() {
                        return;
                    }
                    let ptr = self.ptr;
                    let pdiff = (ptr as usize) - (self.balign as usize);
                    let (p64q, p64r) = (pdiff / 64, pdiff % 64);
                    let mut w = self.wmask.as_ptr().add(p64q);
                    let mut wmask = (*w) & ((!0u64) << p64r);
                    let mut p = self.balign.add(p64q * 64);
                    while p < self.end {
                        if wmask != 0 {
                            p = p.add(wmask.trailing_zeros() as usize);
                            if p < self.end {
                                self.ptr = p.add(1);
                                vec.extend_from_slice(std::slice::from_raw_parts(
                                    ptr,
                                    p as usize - ptr as usize,
                                ));
                                return;
                            }
                            break;
                        }
                        p = p.add(64);
                        w = w.add(1);
                        wmask = *w;
                    }
                    vec.extend_from_slice(std::slice::from_raw_parts(
                        ptr,
                        self.end as usize - ptr as usize,
                    ));
                }
            }
            #[cfg(not(target_arch = "x86_64"))]
            unsafe {
                let ptr = self.ptr;
                let mut p = ptr.add(1);
                while p < self.end {
                    if *p <= b' ' {
                        self.ptr = p.add(1);
                        vec.extend_from_slice(std::slice::from_raw_parts(
                            ptr,
                            p as usize - ptr as usize,
                        ));
                        return;
                    }
                    p = p.add(1);
                }
                vec.extend_from_slice(std::slice::from_raw_parts(ptr, self.end as usize - ptr as usize));
                loop {
                    self.ptr = self.end;
                    if !self.inner_read() {
                        break;
                    }
                    let ptr = self.ptr;
                    let mut p = ptr;
                    while p < self.end {
                        if *p <= b' ' {
                            self.ptr = p.add(1);
                            vec.extend_from_slice(std::slice::from_raw_parts(
                                ptr,
                                p as usize - ptr as usize,
                            ));
                            return;
                        }
                        p = p.add(1);
                    }
                    vec.extend_from_slice(std::slice::from_raw_parts(
                        ptr,
                        self.end as usize - ptr as usize,
                    ));
                }
                return;
            }
        }
        #[inline]
        pub fn next_wordtoken(&mut self) -> Token {
            if !self.skipuntil_bytes_fn(&mut |c: u8| c > b' ') {
                return Token::Slice(b"");
            }
            #[cfg(target_arch = "x86_64")]
            unsafe {
                let ptr = self.ptr;
                let pdiff = (self.ptr as usize) - (self.balign as usize) + 1;
                let (p64q, p64r) = (pdiff / 64, pdiff % 64);
                let mut w = self.wmask.as_ptr().add(p64q);
                let wmask = (*w) & ((!0u64) << p64r);
                let mut p = self.balign.add(p64q * 64);
                if wmask != 0 {
                    p = p.add(wmask.trailing_zeros() as usize);
                    if p < self.end {
                        self.ptr = p.add(1);
                        return Token::Slice(std::slice::from_raw_parts(
                            ptr,
                            p as usize - ptr as usize,
                        ));
                    }
                }
                p = p.add(64);
                w = w.add(1);
                let end64 = self.end.sub(64);
                while p < end64 {
                    let wmask = *w;
                    if wmask != 0 {
                        let tlz = wmask.trailing_zeros();
                        let pp = p.add(tlz as usize);
                        self.ptr = pp.add(1);
                        return Token::Slice(std::slice::from_raw_parts(
                            ptr,
                            pp as usize - ptr as usize,
                        ));
                    }
                    p = p.add(64);
                    w = w.add(1);
                }
                if p < self.end {
                    let wmask = *w;
                    if wmask != 0 {
                        let tlz = wmask.trailing_zeros();
                        let pp = p.add(tlz as usize);
                        if pp < self.end {
                            self.ptr = pp.add(1);
                            return Token::Slice(std::slice::from_raw_parts(
                                ptr,
                                pp as usize - ptr as usize,
                            ));
                        }
                    }
                }
                let mut v =
                    std::slice::from_raw_parts(ptr, self.end as usize - ptr as usize).to_vec();
                loop {
                    self.ptr = self.end;
                    if !self.inner_read() {
                        return Token::Bytes(v);
                    }
                    let ptr = self.ptr;
                    let pdiff = (ptr as usize) - (self.balign as usize);
                    let (p64q, p64r) = (pdiff / 64, pdiff % 64);
                    let mut w = self.wmask.as_ptr().add(p64q);
                    let mut wmask = (*w) & ((!0u64) << p64r);
                    let mut p = self.balign.add(p64q * 64);
                    while p < self.end {
                        if wmask != 0 {
                            p = p.add(wmask.trailing_zeros() as usize);
                            if p < self.end {
                                self.ptr = p.add(1);
                                v.extend_from_slice(std::slice::from_raw_parts(
                                    ptr,
                                    p as usize - ptr as usize,
                                ));
                                return Token::Bytes(v);
                            }
                            break;
                        }
                        p = p.add(64);
                        w = w.add(1);
                        wmask = *w;
                    }
                    v.extend_from_slice(std::slice::from_raw_parts(
                        ptr,
                        self.end as usize - ptr as usize,
                    ));
                }
            }
            #[cfg(not(target_arch = "x86_64"))]
            unsafe {
                let ptr = self.ptr;
                let mut p = ptr.add(1);
                while p < self.end {
                    if *p <= b' ' {
                        self.ptr = p.add(1);
                        return Token::Slice(std::slice::from_raw_parts(
                            ptr,
                            p as usize - ptr as usize,
                        ));
                    }
                    p = p.add(1);
                }
                let mut v =
                    std::slice::from_raw_parts(ptr, self.end as usize - ptr as usize).to_vec();
                loop {
                    self.ptr = self.end;
                    if !self.inner_read() {
                        break;
                    }
                    let ptr = self.ptr;
                    let mut p = ptr;
                    while p < self.end {
                        if *p <= b' ' {
                            self.ptr = p.add(1);
                            v.extend_from_slice(std::slice::from_raw_parts(
                                ptr,
                                p as usize - ptr as usize,
                            ));
                            return Token::Bytes(v);
                        }
                        p = p.add(1);
                    }
                    v.extend_from_slice(std::slice::from_raw_parts(
                        ptr,
                        self.end as usize - ptr as usize,
                    ));
                }
                return Token::Bytes(v);
            }
        }
        #[inline]
        pub fn next_linetoken(&mut self) -> Token {
            if !self.skipuntil_bytes_fn(&mut |c: u8| c >= b' ') {
                return Token::Slice(b"");
            }
            #[cfg(target_arch = "x86_64")]
            unsafe {
                let ptr = self.ptr;
                let pdiff = (self.ptr as usize) - (self.balign as usize) + 1;
                let (p64q, p64r) = (pdiff / 64, pdiff % 64);
                let mut w = self.wmask.as_ptr().add(p64q);
                let mut wmask = (*w) & ((!0u64) << p64r);
                let mut p = self.balign.add(p64q * 64);
                's: /* ' */ while p < self.end {
                    while wmask != 0 {
                        let tlz = wmask.trailing_zeros();
                        let pp = p.add(tlz as usize);
                        if pp >= self.end {
                            break 's; /* ' */
                        }
                        if *pp < b' ' {
                            self.ptr = pp.add(1);
                            return Token::Slice(std::slice::from_raw_parts(
                                ptr,
                                pp as usize - ptr as usize,
                            ));
                        }
                        wmask &= wmask.wrapping_sub(1); // elase least one bit
                    }
                    p = p.add(64);
                    w = w.add(1);
                    wmask = *w;
                }
                let mut v =
                    std::slice::from_raw_parts(ptr, self.end as usize - ptr as usize).to_vec();
                loop {
                    self.ptr = self.end;
                    if !self.inner_read() {
                        break;
                    }
                    let ptr = self.ptr;
                    let pdiff = (ptr as usize) - (self.balign as usize);
                    let (p64q, p64r) = (pdiff / 64, pdiff % 64);
                    let mut w = self.wmask.as_ptr().add(p64q);
                    let mut wmask = (*self.wmask.get_unchecked(p64q)) & ((!0u64) << p64r);
                    let mut p = self.balign.add(p64q * 64);
                    'v: /* ' */ while p < self.end {
                        while wmask != 0 {
                            let tlz = wmask.trailing_zeros();
                            let pp = p.add(tlz as usize);
                            if pp >= self.end {
                                break 'v; /* ' */
                            }
                            assert!(*pp < b' ');
                            if (*pp) < b' ' {
                                self.ptr = pp.add(1);
                                v.extend_from_slice(std::slice::from_raw_parts(
                                    ptr,
                                    pp as usize - ptr as usize,
                                ));
                                return Token::Bytes(v);
                            }
                            wmask &= wmask.wrapping_sub(1); // elase least one bit
                        }
                        p = p.add(64);
                        w = w.add(1);
                        wmask = *w;
                    }
                    v.extend_from_slice(std::slice::from_raw_parts(
                        ptr,
                        self.end as usize - ptr as usize,
                    ));
                }
                return Token::Bytes(v);
            }
            #[cfg(not(target_arch = "x86_64"))]
            unsafe {
                let ptr = self.ptr;
                let mut p = ptr.add(1);
                while p < self.end {
                    if *p < b' ' {
                        self.ptr = p.add(1);
                        return Token::Slice(std::slice::from_raw_parts(
                            ptr,
                            p as usize - ptr as usize,
                        ));
                    }
                    p = p.add(1);
                }
                let mut v =
                    std::slice::from_raw_parts(ptr, self.end as usize - ptr as usize).to_vec();
                loop {
                    self.ptr = self.end;
                    if !self.inner_read() {
                        break;
                    }
                    let ptr = self.ptr;
                    let mut p = ptr;
                    while p < self.end {
                        if *p < b' ' {
                            self.ptr = p.add(1);
                            v.extend_from_slice(std::slice::from_raw_parts(
                                ptr,
                                p as usize - ptr as usize,
                            ));
                            return Token::Bytes(v);
                        }
                        p = p.add(1);
                    }
                    v.extend_from_slice(std::slice::from_raw_parts(
                        ptr,
                        self.end as usize - ptr as usize,
                    ));
                }
                return Token::Bytes(v);
            }
        }
    }
    impl<R: std::io::BufRead> Iterator for ProconIBufIter<R> {
        type Item = u8;
        fn next(&mut self) -> Option<Self::Item> {
            if !self.buf_empty() || unsafe { self.inner_read() } {
                Some(unsafe { self.next_unchecked() })
            } else {
                None
            }
        }
        fn size_hint(&self) -> (usize, Option<usize>) {
            (usize::max_value(), None)
        }
    }
    pub trait UPrimInt:
        Copy
        + Default
        + std::cmp::Ord
        + std::ops::Add<Output = Self>
        + std::ops::Sub<Output = Self>
        + std::ops::Mul<Output = Self>
        + std::ops::Div<Output = Self>
        + std::ops::Rem<Output = Self>
        + std::ops::AddAssign
        + std::ops::SubAssign
        + std::ops::MulAssign
        + std::ops::DivAssign
        + std::ops::RemAssign
        + std::ops::Shl<u32, Output = Self>
        + std::ops::Shr<u32, Output = Self>
        + std::ops::ShlAssign<u32>
        + std::ops::ShrAssign<u32>
        + std::ops::BitAnd<Output = Self>
        + std::ops::BitOr<Output = Self>
        + std::ops::BitXor<Output = Self>
        + std::ops::BitAndAssign
        + std::ops::BitOrAssign
        + std::ops::BitXorAssign
        + std::convert::From<u8>
    {
        const BITS: u32;
        fn count_zeros(self) -> u32;
        fn trailing_zeros(self) -> u32;
        fn leading_zeros(self) -> u32;
    }
    macro_rules! impl_uprimint {
        ($t:ty) => {
            impl UPrimInt for $t {
                const BITS: u32 = (0 as $t).count_zeros();
                fn count_zeros(self) -> u32 {
                    self.count_zeros()
                }
                fn trailing_zeros(self) -> u32 {
                    self.trailing_zeros()
                }
                fn leading_zeros(self) -> u32 {
                    self.leading_zeros()
                }
            }
        };
    }
    impl_uprimint!(u8);
    impl_uprimint!(u16);
    impl_uprimint!(u32);
    impl_uprimint!(u64);
    impl_uprimint!(u128);
    impl_uprimint!(usize);
    pub trait IPrimInt:
        Copy
        + Default
        + std::cmp::Ord
        + std::ops::Add<Output = Self>
        + std::ops::Sub<Output = Self>
        + std::ops::Neg<Output = Self>
        + std::ops::Mul<Output = Self>
        + std::ops::Div<Output = Self>
        + std::ops::Rem<Output = Self>
        + std::convert::From<i8>
    {
        const BITS: u32;
    }
    macro_rules! impl_iprimint {
        ($t:ty) => {
            impl IPrimInt for $t {
                const BITS: u32 = (0 as $t).count_zeros();
            }
        };
    }
    impl_iprimint!(i8);
    impl_iprimint!(i16);
    impl_iprimint!(i32);
    impl_iprimint!(i64);
    impl_iprimint!(i128);
    impl_iprimint!(isize);

    #[inline]
    fn parseuint_arith8le(mut a: u64) -> u64 {
        a = (a & 0x0f0f0f0f0f0f0f0f).wrapping_mul((10 << 8) + 1) >> 8;
        a = (a & 0x00ff00ff00ff00ff).wrapping_mul((100 << 16) + 1) >> 16;
        (a & 0x0000ffff0000ffff).wrapping_mul((10000 << 32) + 1) >> 32
    }
    #[inline]
    #[allow(unused)]
    fn parseuint_arith8be(mut a: u64) -> u64 {
        a = (a & 0x0f0f0f0f0f0f0f0f).wrapping_mul((1 << 8) + 10) >> 8;
        a = (a & 0x00ff00ff00ff00ff).wrapping_mul((1 << 16) + 100) >> 16;
        (a & 0x0000ffff0000ffff).wrapping_mul((1 << 32) + 10000) >> 32
    }
    #[inline]
    fn parseuint_arith4le(mut a: u32) -> u32 {
        a = (a & 0x0f0f0f0f).wrapping_mul((10 << 8) + 1) >> 8;
        (a & 0x00ff00ff).wrapping_mul((100 << 16) + 1) >> 16
    }
    #[inline]
    #[allow(unused)]
    fn parseuint_arith4be(mut a: u32) -> u32 {
        a = (a & 0x0f0f0f0f).wrapping_mul((1 << 8) + 10) >> 8;
        (a & 0x00ff00ff).wrapping_mul((1 << 16) + 100) >> 16
    }
    #[inline]
    fn parseuint_raw32b(s: [u8; 32]) -> u128 {
        use std::convert::TryInto;
        let a = parseuint_arith8le(u64::from_le_bytes(s[0..8].try_into().unwrap()));
        let b = parseuint_arith8le(u64::from_le_bytes(s[8..16].try_into().unwrap()));
        let c = parseuint_arith8le(u64::from_le_bytes(s[16..24].try_into().unwrap()));
        let d = parseuint_arith8le(u64::from_le_bytes(s[24..32].try_into().unwrap()));
        ((a * 100000000 + b) as u128) * 10000000000000000 + ((c * 100000000 + d) as u128)
    }
    #[inline]
    fn parseuint_raw16b(s: [u8; 16]) -> u64 {
        use std::convert::TryInto;
        let a = parseuint_arith8le(u64::from_le_bytes(s[0..8].try_into().unwrap()));
        let b = parseuint_arith8le(u64::from_le_bytes(s[8..16].try_into().unwrap()));
        a * 100000000 + b
    }
    #[inline]
    fn parseuint_raw8b(s: [u8; 8]) -> u64 {
        parseuint_arith8le(u64::from_le_bytes(s))
    }
    #[inline]
    fn parseuint_raw7b(s: &[u8]) -> u64 {
        debug_assert!(s.len() < 8);
        let (s3, s4) = s.split_at(s.len() % 4);
        let mut r = s3.iter().fold(0, |p, &c| p * 10 + (c & 0x0f) as u64);
        if s4.len() == 4 {
            r = r * 10000 + (parseuint_arith4le(u32::from_le_bytes(s4.try_into().unwrap())) as u64)
        }
        r
    }
    #[inline]
    fn parseuint_raw4b(s: [u8; 4]) -> u32 {
        parseuint_arith4le(u32::from_le_bytes(s))
    }
    #[inline]
    fn parseuint_raw3b(s: &[u8]) -> u32 {
        s.iter().fold(0, |p, &c| p * 10 + ((c & 0x0f) as u32))
    }
    pub trait ByteParseIntRaw {
        fn parse_u128_raw(&self) -> u128;
        fn parse_u64_raw(&self) -> u64;
        fn parse_u32_raw(&self) -> u32;
        fn parse_u16_raw(&self) -> u16;
        fn parse_u8_raw(&self) -> u8;
        fn parse_i128_raw(&self) -> i128;
        fn parse_i64_raw(&self) -> i64;
        fn parse_i32_raw(&self) -> i32;
        fn parse_i16_raw(&self) -> i16;
        fn parse_i8_raw(&self) -> i8;
        fn parse_u128_rawopt(&self) -> Option<u128>;
        fn parse_u64_rawopt(&self) -> Option<u64>;
        fn parse_u32_rawopt(&self) -> Option<u32>;
        fn parse_u16_rawopt(&self) -> Option<u16>;
        fn parse_u8_rawopt(&self) -> Option<u8>;
    }
    impl ByteParseIntRaw for &[u8] {
        // parse_u128_raw: empty or int(self) > u128::MAX or self.len() > 39 or !self.iter().all(u8::is_ascii_digit) will cause Undefined Behavior.
        fn parse_u128_raw(&self) -> u128 {
            use std::convert::TryInto;
            debug_assert!(!self.is_empty());
            debug_assert!(self.len() <= 39);
            debug_assert!(self.iter().all(u8::is_ascii_digit));
            let (s15, s16) = self.split_at(self.len() % 16);
            let r = match s15.len() / 4 {
                0 => s15.iter().fold(0, |p, &c| p * 10 + ((c & 0x0f) as u64)),
                1 => {
                    if s15.len() < 4 {
                        unsafe { core::hint::unreachable_unchecked() }
                    }
                    s15[4..].iter().fold(
                        parseuint_raw4b(s15[0..4].try_into().unwrap()) as u64,
                        |p, &c| p * 10 + ((c & 0x0f) as u64),
                    )
                }
                2 => {
                    if s15.len() < 8 {
                        unsafe { core::hint::unreachable_unchecked() }
                    }
                    s15[8..]
                        .iter()
                        .fold(parseuint_raw8b(s15[0..8].try_into().unwrap()), |p, &c| {
                            p * 10 + ((c & 0x0f) as u64)
                        })
                }
                _ => {
                    if s15.len() < 12 {
                        unsafe { core::hint::unreachable_unchecked() }
                    }
                    s15[12..].iter().fold(
                        parseuint_raw8b(s15[0..8].try_into().unwrap()) * 10000
                            + parseuint_raw4b(s15[8..12].try_into().unwrap()) as u64,
                        |p, &c| p * 10 + ((c & 0x0f) as u64),
                    )
                }
            };
            match s16.len() {
                0 => r as u128,
                16 => {
                    (r as u128) * 10000000000000000
                        + parseuint_raw16b(s16.try_into().unwrap()) as u128
                }
                32 => {
                    (r as u128) * 100000000000000000000000000000000
                        + parseuint_raw32b(s16.try_into().unwrap())
                }
                _ => unsafe { core::hint::unreachable_unchecked() },
            }
        }
        // parse_u64_raw: empty or int(self) > u64::MAX or self.len() > 20 or !self.iter().all(u8::is_ascii_digit) will cause Undefined Behavior.
        fn parse_u64_raw(&self) -> u64 {
            use std::convert::TryInto;
            debug_assert!(!self.is_empty());
            debug_assert!(self.len() <= 20);
            debug_assert!(self.iter().all(u8::is_ascii_digit));
            match self.len() / 4 {
                0 => self.iter().fold(0, |p, &c| p * 10 + ((c & 0x0f) as u64)),
                1 => {
                    if self.len() < 4 {
                        unsafe { core::hint::unreachable_unchecked() }
                    }
                    self[4..].iter().fold(
                        parseuint_raw4b(self[0..4].try_into().unwrap()) as u64,
                        |p, &c| p * 10 + ((c & 0x0f) as u64),
                    )
                }
                2 => {
                    if self.len() < 8 {
                        unsafe { core::hint::unreachable_unchecked() }
                    }
                    self[8..]
                        .iter()
                        .fold(parseuint_raw8b(self[0..8].try_into().unwrap()), |p, &c| {
                            p * 10 + ((c & 0x0f) as u64)
                        })
                }
                3 => {
                    if self.len() < 12 {
                        unsafe { core::hint::unreachable_unchecked() }
                    }
                    self[12..].iter().fold(
                        parseuint_raw8b(self[0..8].try_into().unwrap()) * 10000
                            + parseuint_raw4b(self[8..12].try_into().unwrap()) as u64,
                        |p, &c| p * 10 + ((c & 0x0f) as u64),
                    )
                }
                4 => {
                    if self.len() < 16 {
                        unsafe { core::hint::unreachable_unchecked() }
                    }
                    self[16..].iter().fold(
                        parseuint_raw16b(self[0..16].try_into().unwrap()),
                        |p, &c| p * 10 + ((c & 0x0f) as u64),
                    )
                }
                _ => {
                    if self.len() < 20 {
                        unsafe { core::hint::unreachable_unchecked() }
                    }
                    parseuint_raw16b(self[0..16].try_into().unwrap()) * 10000
                        + (parseuint_raw4b(self[16..20].try_into().unwrap()) as u64)
                }
            }
        }
        // parse_u32_raw: empty or int(self) > u32::MAX or self.len() > 10 or !self.iter().all(u8::is_ascii_digit) will cause Undefined Behavior.
        fn parse_u32_raw(&self) -> u32 {
            use std::convert::TryInto;
            debug_assert!(!self.is_empty());
            debug_assert!(self.len() <= 10);
            debug_assert!(self.iter().all(u8::is_ascii_digit));
            match self.len() / 4 {
                0 => self.iter().fold(0, |p, &c| p * 10 + ((c & 0x0f) as u32)),
                1 => {
                    if self.len() < 4 {
                        unsafe { core::hint::unreachable_unchecked() }
                    }
                    self[4..].iter().fold(
                        parseuint_raw4b(self[0..4].try_into().unwrap()) as u32,
                        |p, &c| p * 10 + ((c & 0x0f) as u32),
                    )
                }
                _ => {
                    if self.len() < 8 {
                        unsafe { core::hint::unreachable_unchecked() }
                    }
                    self[8..].iter().fold(
                        parseuint_raw8b(self[0..8].try_into().unwrap()) as u32,
                        |p, &c| p * 10 + ((c & 0x0f) as u32),
                    )
                }
            }
        }
        // parse_u16_raw: empty or int(self) > u16::MAX or self.len() > 5 or !self.iter().all(u8::is_ascii_digit) will cause Undefined Behavior.
        fn parse_u16_raw(&self) -> u16 {
            use std::convert::TryInto;
            debug_assert!(!self.is_empty());
            debug_assert!(self.len() <= 5);
            debug_assert!(self.iter().all(u8::is_ascii_digit));
            parseuint_raw7b(&self) as u16
        }
        // parse_u8_raw: empty or int(self) > u8::MAX or self.len() > 3 or !self.iter().all(u8::is_ascii_digit) will cause Undefined Behavior.
        fn parse_u8_raw(&self) -> u8 {
            debug_assert!(!self.is_empty());
            debug_assert!(self.len() <= 3);
            debug_assert!(self.iter().all(u8::is_ascii_digit));
            parseuint_raw3b(&self) as u8
        }
        fn parse_i128_raw(&self) -> i128 {
            debug_assert!(!self.is_empty());
            if self.is_empty() {
                0
            } else if self[0] == b'-' {
                (&self[1..]).parse_u128_raw().wrapping_neg() as i128
            } else {
                self.parse_u128_raw() as i128
            }
        }
        fn parse_i64_raw(&self) -> i64 {
            debug_assert!(!self.is_empty());
            if self.is_empty() {
                0
            } else if self[0] == b'-' {
                (&self[1..]).parse_u64_raw().wrapping_neg() as i64
            } else {
                self.parse_u64_raw() as i64
            }
        }
        fn parse_i32_raw(&self) -> i32 {
            debug_assert!(!self.is_empty());
            if self.is_empty() {
                0
            } else if self[0] == b'-' {
                (&self[1..]).parse_u32_raw().wrapping_neg() as i32
            } else {
                self.parse_u32_raw() as i32
            }
        }
        fn parse_i16_raw(&self) -> i16 {
            debug_assert!(!self.is_empty());
            if self.is_empty() {
                0
            } else if self[0] == b'-' {
                (&self[1..]).parse_u16_raw().wrapping_neg() as i16
            } else {
                self.parse_u16_raw() as i16
            }
        }
        fn parse_i8_raw(&self) -> i8 {
            debug_assert!(!self.is_empty());
            if self.is_empty() {
                0
            } else if self[0] == b'-' {
                (&self[1..]).parse_u128_raw().wrapping_neg() as i8
            } else {
                self.parse_u128_raw() as i8
            }
        }
        // parse_u128_rawopt: empty or int(self) > u128::MAX or self.len() > 39 or !self.iter().all(u8::is_ascii_digit) will cause Undefined Behavior.
        fn parse_u128_rawopt(&self) -> Option<u128> {
            use std::convert::TryInto;
            debug_assert!(!self.is_empty());
            debug_assert!(self.len() <= 39);
            debug_assert!(self.iter().all(u8::is_ascii_digit));
            let (s15, s16) = self.split_at(self.len() % 16);
            let r = match s15.len() / 4 {
                0 => s15.iter().fold(0, |p, &c| p * 10 + ((c & 0x0f) as u64)),
                1 => {
                    if s15.len() < 4 {
                        unsafe { core::hint::unreachable_unchecked() }
                    }
                    s15[4..].iter().fold(
                        parseuint_raw4b(s15[0..4].try_into().unwrap()) as u64,
                        |p, &c| p * 10 + ((c & 0x0f) as u64),
                    )
                }
                2 => {
                    if s15.len() < 8 {
                        unsafe { core::hint::unreachable_unchecked() }
                    }
                    s15[8..]
                        .iter()
                        .fold(parseuint_raw8b(s15[0..8].try_into().unwrap()), |p, &c| {
                            p * 10 + ((c & 0x0f) as u64)
                        })
                }
                _ => {
                    if s15.len() < 12 {
                        unsafe { core::hint::unreachable_unchecked() }
                    }
                    s15[12..].iter().fold(
                        parseuint_raw8b(s15[0..8].try_into().unwrap()) * 10000
                            + parseuint_raw4b(s15[8..12].try_into().unwrap()) as u64,
                        |p, &c| p * 10 + ((c & 0x0f) as u64),
                    )
                }
            };
            match s16.len() {
                0 => Some(r as u128),
                16 => Some(
                    (r as u128) * 10000000000000000
                        + parseuint_raw16b(s16.try_into().unwrap()) as u128,
                ),
                32 => (r as u128)
                    .checked_mul(100000000000000000000000000000000)?
                    .checked_add(parseuint_raw32b(s16.try_into().unwrap())),
                _ => None,
            }
        }
        // parse_u64_rawopt: empty or int(self) > u64::MAX or self.len() > 20 or !self.iter().all(u8::is_ascii_digit) will cause Undefined Behavior.
        fn parse_u64_rawopt(&self) -> Option<u64> {
            use std::convert::TryInto;
            debug_assert!(!self.is_empty());
            debug_assert!(self.len() <= 20);
            debug_assert!(self.iter().all(u8::is_ascii_digit));
            match self.len() / 4 {
                0 => Some(self.iter().fold(0, |p, &c| p * 10 + ((c & 0x0f) as u64))),
                1 => {
                    if self.len() < 4 {
                        unsafe { core::hint::unreachable_unchecked() }
                    }
                    Some(self[4..].iter().fold(
                        parseuint_raw4b(self[0..4].try_into().unwrap()) as u64,
                        |p, &c| p * 10 + ((c & 0x0f) as u64),
                    ))
                }
                2 => {
                    if self.len() < 8 {
                        unsafe { core::hint::unreachable_unchecked() }
                    }
                    Some(
                        self[8..]
                            .iter()
                            .fold(parseuint_raw8b(self[0..8].try_into().unwrap()), |p, &c| {
                                p * 10 + ((c & 0x0f) as u64)
                            }),
                    )
                }
                3 => {
                    if self.len() < 12 {
                        unsafe { core::hint::unreachable_unchecked() }
                    }
                    Some(self[12..].iter().fold(
                        parseuint_raw8b(self[0..8].try_into().unwrap()) * 10000
                            + parseuint_raw4b(self[8..12].try_into().unwrap()) as u64,
                        |p, &c| p * 10 + ((c & 0x0f) as u64),
                    ))
                }
                4 => {
                    if self.len() < 16 {
                        unsafe { core::hint::unreachable_unchecked() }
                    }
                    Some(self[16..].iter().fold(
                        parseuint_raw16b(self[0..16].try_into().unwrap()),
                        |p, &c| p * 10 + ((c & 0x0f) as u64),
                    ))
                }
                5 => {
                    if self.len() < 20 {
                        unsafe { core::hint::unreachable_unchecked() }
                    }
                    self[20..].iter().fold(
                        parseuint_raw16b(self[0..16].try_into().unwrap())
                            .checked_mul(10000)?
                            .checked_add(parseuint_raw4b(self[16..20].try_into().unwrap()) as u64),
                        |p, &c| p?.checked_mul(10)?.checked_add((c & 0x0f) as u64),
                    )
                }
                _ => None,
            }
        }
        // parse_u32_rawopt: empty or int(self) > u32::MAX or self.len() > 10 or !self.iter().all(u8::is_ascii_digit) will cause Undefined Behavior.
        fn parse_u32_rawopt(&self) -> Option<u32> {
            use std::convert::TryInto;
            debug_assert!(!self.is_empty());
            debug_assert!(self.len() <= 10);
            debug_assert!(self.iter().all(u8::is_ascii_digit));
            match self.len() / 4 {
                0 => Some(self.iter().fold(0, |p, &c| p * 10 + ((c & 0x0f) as u32))),
                1 => {
                    if self.len() < 4 {
                        unsafe { core::hint::unreachable_unchecked() }
                    }
                    Some(self[4..].iter().fold(
                        parseuint_raw4b(self[0..4].try_into().unwrap()) as u32,
                        |p, &c| p * 10 + ((c & 0x0f) as u32),
                    ))
                }
                2 => {
                    if self.len() < 8 {
                        unsafe { core::hint::unreachable_unchecked() }
                    }
                    self[8..].iter().fold(
                        Some(parseuint_raw8b(self[0..8].try_into().unwrap()) as u32),
                        |p, &c| p?.checked_mul(10)?.checked_add((c & 0x0f) as u32),
                    )
                }
                _ => None,
            }
        }
        // parse_u16_rawopt: empty or int(self) > u16::MAX or self.len() > 5 or !self.iter().all(u8::is_ascii_digit) will cause Undefined Behavior.
        fn parse_u16_rawopt(&self) -> Option<u16> {
            use std::convert::TryInto;
            debug_assert!(!self.is_empty());
            debug_assert!(self.len() <= 5);
            debug_assert!(self.iter().all(u8::is_ascii_digit));
            match self.len() / 4 {
                0 => Some(self.iter().fold(0, |p, &c| p * 10 + ((c & 0x0f) as u16))),
                1 => {
                    if self.len() < 4 {
                        unsafe { core::hint::unreachable_unchecked() }
                    }
                    self[4..].iter().fold(
                        Some(parseuint_raw4b(self[0..4].try_into().unwrap()) as u16),
                        |p, &c| p?.checked_mul(10)?.checked_add((c & 0x0f) as u16),
                    )
                }
                _ => None,
            }
        }
        // parse_u8_rawopt: empty or int(self) > u8::MAX or self.len() > 3 or !self.iter().all(u8::is_ascii_digit) will cause Undefined Behavior.
        fn parse_u8_rawopt(&self) -> Option<u8> {
            use std::convert::TryInto;
            debug_assert!(!self.is_empty());
            debug_assert!(self.len() <= 3);
            debug_assert!(self.iter().all(u8::is_ascii_digit));
            match self.len() {
                0..=2 => Some(self.iter().fold(0, |p, &c| p * 10 + (c & 0x0f))),
                3 => ((self[0] & 0x0f) * 10 + (self[1] & 0x0f))
                    .checked_mul(10)?
                    .checked_add(self[2] & 0x0f),
                _ => None,
            }
        }
    }
    /// speed frenzy input parser for program compete
    pub trait ProconParse {
        fn get_ascii_byte(&mut self) -> u8 {
            self.get_ascii_byte_opt().unwrap()
        }
        fn get_ascii_byte_or_default(&mut self) -> u8 {
            self.get_ascii_byte_opt().unwrap_or_default()
        }
        fn get_ascii_byte_opt(&mut self) -> Option<u8>;
        fn parse_uint<U: UPrimInt>(&mut self) -> U {
            self.parse_uint_opt().unwrap()
        }
        fn parse_uint_or_default<U: UPrimInt>(&mut self) -> U {
            self.parse_uint_opt().unwrap_or_default()
        }
        fn parse_uint_opt<U: UPrimInt>(&mut self) -> Option<U>;
        fn parse_iint<I: IPrimInt>(&mut self) -> I {
            self.parse_iint_opt().unwrap()
        }
        fn parse_iint_or_default<I: IPrimInt>(&mut self) -> I {
            self.parse_iint_opt().unwrap_or_default()
        }
        fn parse_iint_opt<I: IPrimInt>(&mut self) -> Option<I>;
    }
    impl<T: Iterator<Item = u8>> ProconParse for T {
        fn get_ascii_byte_opt(&mut self) -> Option<u8> {
            loop {
                match self.next() {
                    Some(c @ 0x21..=0x7e) => {
                        return Some(c);
                    }
                    Some(_) => continue,
                    _ => return None,
                }
            }
        }
        fn parse_uint_opt<U: UPrimInt>(&mut self) -> Option<U> {
            loop {
                match self.next() {
                    Some(c @ b'0'..=b'9') => {
                        let mut v = U::from(c - b'0');
                        while let Some(c @ b'0'..=b'9') = self.next() {
                            v = v * U::from(10) + U::from(c - b'0');
                        }
                        return Some(v);
                    }
                    Some(_) => continue,
                    _ => return None,
                }
            }
        }
        fn parse_iint_opt<I: IPrimInt>(&mut self) -> Option<I> {
            loop {
                match self.next() {
                    Some(c @ b'0'..=b'9') => {
                        let mut v = I::from((c - b'0') as i8);
                        while let Some(c @ b'0'..=b'9') = self.next() {
                            v = v * I::from(10) + I::from((c - b'0') as i8);
                        }
                        return Some(v);
                    }
                    Some(b'-') => match self.next() {
                        Some(c @ b'0'..=b'9') => {
                            let mut v = I::from(-((c - b'0') as i8));
                            while let Some(c @ b'0'..=b'9') = self.next() {
                                v = v * I::from(10) - I::from((c - b'0') as i8);
                            }
                            return Some(v);
                        }
                        _ => return None,
                    },
                    Some(_) => continue,
                    _ => return None,
                }
            }
        }
    }
    impl<R: std::io::BufRead> Drop for ProconIBufIter<R> {
        /// Saving the pointer on interruption
        fn drop(&mut self) {
            self.inner
                .consume(unsafe { ptr_offset_u8(self.ptr, self.raw) });
        }
    }
    /// Insufficient write buffer size causes undefined operation.
    pub struct ProconWriteBuffer(*mut u8, Vec<u8>, [u8; 40000]);
    impl ProconWriteBuffer {
        pub fn with_capacity(capacity: usize) -> Self {
            let mut b = Vec::<u8>::with_capacity(capacity);
            let ptr = b.as_mut_ptr();
            let mut t = [0u8; 40000];
            for i in 0..10000 {
                t[i * 4 + 0] = b'0' + ((i / 100) / 10) as u8;
                t[i * 4 + 1] = b'0' + ((i / 100) % 10) as u8;
                t[i * 4 + 2] = b'0' + ((i % 100) / 10) as u8;
                t[i * 4 + 3] = b'0' + ((i % 100) % 10) as u8;
            }
            Self(ptr, b, t)
        }
        pub fn get_mut_ptr(&self) -> *mut u8 {
            self.0
        }
        pub fn set_mut_ptr(&mut self, p: *mut u8) {
            self.0 = p;
        }
        fn decision(&mut self) {
            let bptr = self.1.as_mut_ptr();
            unsafe { self.1.set_len((self.0 as usize) - (bptr as usize)) };
        }
        pub fn clear(&mut self) {
            self.1.clear();
            self.0 = self.1.as_mut_ptr();
        }
        pub fn get_slice(&mut self) -> &[u8] {
            self.decision();
            self.1.as_slice()
        }
        pub fn reserve(&mut self, additional: usize) {
            self.decision();
            self.1.reserve(additional);
            self.0 = self.1.as_mut_ptr();
        }
        pub fn reserve_exact(&mut self, additional: usize) {
            self.decision();
            self.1.reserve_exact(additional);
            self.0 = self.1.as_mut_ptr();
        }
        pub fn uint<U>(&mut self, d: U)
        where
            U: UPrimInt + std::convert::Into<u128>,
        {
            proconwritebuf_uint(&mut self.0, &self.2, d);
        }
        pub fn uint_sp<U>(&mut self, s: &[U])
        where
            U: UPrimInt + std::convert::Into<u128>,
        {
            let mut p = self.0;
            let mut it = s.iter();
            if let Some(&d) = it.next() {
                proconwritebuf_uint(&mut p, &self.2, d);
                for &d in it {
                    proconwritebuf_sp(&mut p);
                    proconwritebuf_uint(&mut p, &self.2, d);
                }
            }
            self.0 = p;
        }
        pub fn uint_splf<U>(&mut self, s: &[U])
        where
            U: UPrimInt + std::convert::Into<u128>,
        {
            let mut p = self.0;
            let mut it = s.iter();
            if let Some(&d) = it.next() {
                proconwritebuf_uint(&mut p, &self.2, d);
                for &d in it {
                    proconwritebuf_sp(&mut p);
                    proconwritebuf_uint(&mut p, &self.2, d);
                }
            }
            proconwritebuf_lf(&mut p);
            self.0 = p;
        }
        pub fn usize(&mut self, d: usize) {
            proconwritebuf_uint(&mut self.0, &self.2, d as u64);
        }
        pub fn usize_sp(&mut self, s: &[usize]) {
            let mut p = self.0;
            let mut it = s.iter();
            if let Some(&d) = it.next() {
                proconwritebuf_uint(&mut p, &self.2, d as u64);
                for &d in it {
                    proconwritebuf_sp(&mut p);
                    proconwritebuf_uint(&mut p, &self.2, d as u64);
                }
            }
            self.0 = p;
        }
        pub fn usize_splf(&mut self, s: &[usize]) {
            let mut p = self.0;
            let mut it = s.iter();
            if let Some(&d) = it.next() {
                proconwritebuf_uint(&mut p, &self.2, d as u64);
                for &d in it {
                    proconwritebuf_sp(&mut p);
                    proconwritebuf_uint(&mut p, &self.2, d as u64);
                }
            }
            proconwritebuf_lf(&mut p);
            self.0 = p;
        }
        pub fn iint<I>(&mut self, d: I)
        where
            I: IPrimInt + std::convert::Into<i128>,
        {
            proconwritebuf_iint(&mut self.0, &self.2, d);
        }
        pub fn iint_sp<I>(&mut self, s: &[I])
        where
            I: IPrimInt + std::convert::Into<i128>,
        {
            let mut p = self.0;
            let mut it = s.iter();
            if let Some(&d) = it.next() {
                proconwritebuf_iint(&mut p, &self.2, d);
                for &d in it {
                    proconwritebuf_sp(&mut p);
                    proconwritebuf_iint(&mut p, &self.2, d);
                }
            }
            self.0 = p;
        }
        pub fn iint_splf<I>(&mut self, s: &[I])
        where
            I: IPrimInt + std::convert::Into<i128> + std::convert::TryInto<u8>,
        {
            let mut p = self.0;
            let mut it = s.iter();
            if let Some(&d) = it.next() {
                proconwritebuf_iint(&mut p, &self.2, d);
                for &d in it {
                    proconwritebuf_sp(&mut p);
                    proconwritebuf_iint(&mut p, &self.2, d);
                }
            }
            proconwritebuf_lf(&mut p);
            self.0 = p;
        }
        pub fn sp(&mut self) {
            proconwritebuf_sp(&mut self.0);
        }
        pub fn lf(&mut self) {
            proconwritebuf_lf(&mut self.0);
        }
        pub fn bytes(&mut self, s: &[u8]) {
            proconwritebuf_bytes(&mut self.0, s);
        }
        pub fn str(&mut self, s: &str) {
            proconwritebuf_str(&mut self.0, s);
        }
        pub fn string(&mut self, s: &String) {
            proconwritebuf_string(&mut self.0, s);
        }
        pub fn write_all<W>(&mut self, out: &mut W)
        where
            W: std::io::Write,
        {
            self.decision();
            let _ = out.write_all(self.1.as_slice());
            self.1.clear();
            self.0 = self.1.as_mut_ptr();
        }
    }
    pub fn proconwritebuf_uint<U>(p: &mut *mut u8, b: &[u8; 40000], d: U)
    where
        U: UPrimInt + std::convert::Into<u128>,
    {
        unsafe {
            unsafe fn upper(s: *mut u8, b: &[u8; 40000], x: usize) -> usize {
                if x < 100 {
                    if x < 10 {
                        s.copy_from_nonoverlapping(b.as_ptr().add(x * 4 + 3), 1);
                        1
                    } else {
                        s.copy_from_nonoverlapping(b.as_ptr().add(x * 4 + 2), 2);
                        2
                    }
                } else {
                    if x < 1000 {
                        s.copy_from_nonoverlapping(b.as_ptr().add(x * 4 + 1), 3);
                        3
                    } else {
                        s.copy_from_nonoverlapping(b.as_ptr().add(x * 4), 4);
                        4
                    }
                }
            }
            unsafe fn lower(s: *mut u8, b: &[u8; 40000], x: usize) {
                s.copy_from_nonoverlapping(b.as_ptr().add(x * 4), 4);
            }
            let v = std::convert::Into::<u128>::into(d);
            if v < 1_0000_0000_0000_0000_0000_0000_0000_0000 {
                if v < 1_0000_0000_0000_0000 {
                    if v < 1_0000_0000 {
                        if v < 1_0000 {
                            *p = (*p).add(upper(*p, b, v as usize))
                        } else {
                            let (x1, x0) = ((v / 1_0000) as usize, (v % 1_0000) as usize);
                            *p = (*p).add(upper(*p, b, x1));
                            lower(*p, b, x0);
                            *p = (*p).add(4);
                        }
                    } else if v < 1_0000_0000_0000 {
                        let (x2, y0) = ((v / 1_0000_0000) as usize, (v % 1_0000_0000) as usize);
                        *p = (*p).add(upper(*p, b, x2));
                        let (x1, x0) = (y0 / 1_0000, y0 % 1_0000);
                        lower((*p).add(0), b, x1);
                        lower((*p).add(4), b, x0);
                        *p = (*p).add(8);
                    } else {
                        let (y1, y0) = ((v / 1_0000_0000) as usize, (v % 1_0000_0000) as usize);
                        let (x3, x2) = (y1 / 1_0000, y1 % 1_0000);
                        *p = (*p).add(upper(*p, b, x3));
                        lower((*p).add(0), b, x2);
                        let (x1, x0) = (y0 / 1_0000, y0 % 1_0000);
                        lower((*p).add(4), b, x1);
                        lower((*p).add(8), b, x0);
                        *p = (*p).add(12);
                    }
                } else if v < 1_0000_0000_0000_0000_0000_0000 {
                    if v < 1_0000_0000_0000_0000_0000 {
                        let (x4, z0) = ((v / 1_0000_0000_0000_0000) as usize, (v % 1_0000_0000_0000_0000) as usize);
                        *p = (*p).add(upper(*p, b, x4));
                        let (y1, y0) = (z0 / 1_0000_0000, z0 % 1_0000_0000);
                        let (x3, x2) = (y1 / 1_0000, y1 % 1_0000);
                        lower((*p).add(0), b, x3);
                        lower((*p).add(4), b, x2);
                        let (x1, x0) = (y0 / 1_0000, y0 % 1_0000);
                        lower((*p).add(8), b, x1);
                        lower((*p).add(12), b, x0);
                        *p = (*p).add(16);
                    } else {
                        let (y2, z0) = ((v / 1_0000_0000_0000_0000) as usize, (v % 1_0000_0000_0000_0000) as usize);
                        let (x5, x4) = (y2 / 1_0000, y2 % 1_0000);
                        *p = (*p).add(upper(*p, b, x5));
                        lower((*p).add(0), b, x4);
                        let (y1, y0) = (z0 / 1_0000_0000, z0 % 1_0000_0000);
                        let (x3, x2) = (y1 / 1_0000, y1 % 1_0000);
                        lower((*p).add(4), b, x3);
                        lower((*p).add(8), b, x2);
                        let (x1, x0) = (y0 / 1_0000, y0 % 1_0000);
                        lower((*p).add(12), b, x1);
                        lower((*p).add(16), b, x0);
                        *p = (*p).add(20);
                    }
                } else if v < 1_0000_0000_0000_0000_0000_0000_0000 {
                    let (z1, z0) = ((v / 1_0000_0000_0000_0000) as usize, (v % 1_0000_0000_0000_0000) as usize);
                    let (x6, y2) = (z1 / 1_0000_0000, z1 % 1_0000_0000);
                    *p = (*p).add(upper(*p, b, x6));
                    let (x5, x4) = (y2 / 1_0000, y2 % 1_0000);
                    lower((*p).add(0), b, x5);
                    lower((*p).add(4), b, x4);
                    let (y1, y0) = (z0 / 1_0000_0000, z0 % 1_0000_0000);
                    let (x3, x2) = (y1 / 1_0000, y1 % 1_0000);
                    lower((*p).add(8), b, x3);
                    lower((*p).add(12), b, x2);
                    let (x1, x0) = (y0 / 1_0000, y0 % 1_0000);
                    lower((*p).add(16), b, x1);
                    lower((*p).add(20), b, x0);
                    *p = (*p).add(24);
                } else {
                    let (z1, z0) = ((v / 1_0000_0000_0000_0000) as usize, (v % 1_0000_0000_0000_0000) as usize);
                    let (y3, y2) = (z1 / 1_0000_0000, z1 % 1_0000_0000);
                    let (x7, x6) = (y3 / 1_0000, y3 % 1_0000);
                    *p = (*p).add(upper(*p, b, x7));
                    lower((*p).add(0), b, x6);
                    let (x5, x4) = (y2 / 1_0000, y2 % 1_0000);
                    lower((*p).add(4), b, x5);
                    lower((*p).add(8), b, x4);
                    let (y1, y0) = (z0 / 1_0000_0000, z0 % 1_0000_0000);
                    let (x3, x2) = (y1 / 1_0000, y1 % 1_0000);
                    lower((*p).add(12), b, x3);
                    lower((*p).add(16), b, x2);
                    let (x1, x0) = (y0 / 1_0000, y0 % 1_0000);
                    lower((*p).add(20), b, x1);
                    lower((*p).add(24), b, x0);
                    *p = (*p).add(28);
                }
            } else if v < 1_0000_0000_0000_0000_0000_0000_0000_0000_0000 {
                let q = v / 1_0000_0000_0000_0000_0000_0000_0000_0000;
                let r = v - q * 1_0000_0000_0000_0000_0000_0000_0000_0000;
                let x8 = q as usize;
                *p = (*p).add(upper(*p, b, x8));
                let (z1, z0) = ((r / 1_0000_0000_0000_0000) as usize, (r % 1_0000_0000_0000_0000) as usize);
                let (y3, y2) = (z1 / 1_0000_0000, z1 % 1_0000_0000);
                let (x7, x6) = (y3 / 1_0000, y3 % 1_0000);
                lower((*p).add(0), b, x7);
                lower((*p).add(4), b, x6);
                let (x5, x4) = (y2 / 1_0000, y2 % 1_0000);
                lower((*p).add(8), b, x5);
                lower((*p).add(12), b, x4);
                let (y1, y0) = (z0 / 1_0000_0000, z0 % 1_0000_0000);
                let (x3, x2) = (y1 / 1_0000, y1 % 1_0000);
                lower((*p).add(16), b, x3);
                lower((*p).add(20), b, x2);
                let (x1, x0) = (y0 / 1_0000, y0 % 1_0000);
                lower((*p).add(24), b, x1);
                lower((*p).add(28), b, x0);
                *p = (*p).add(32);
            } else {
                let q = v / 1_0000_0000_0000_0000_0000_0000_0000_0000;
                let r = v - q * 1_0000_0000_0000_0000_0000_0000_0000_0000;
                let (x9, x8) = ((q as usize) / 1_0000, (q as usize) % 1_0000);
                *p = (*p).add(upper(*p, b, x9));
                lower((*p).add(0), b, x8);
                let (z1, z0) = ((r / 1_0000_0000_0000_0000) as usize, (r % 1_0000_0000_0000_0000) as usize);
                let (y3, y2) = (z1 / 1_0000_0000, z1 % 1_0000_0000);
                let (x7, x6) = (y3 / 1_0000, y3 % 1_0000);
                lower((*p).add(4), b, x7);
                lower((*p).add(8), b, x6);
                let (x5, x4) = (y2 / 1_0000, y2 % 1_0000);
                lower((*p).add(12), b, x5);
                lower((*p).add(16), b, x4);
                let (y1, y0) = (z0 / 1_0000_0000, z0 % 1_0000_0000);
                let (x3, x2) = (y1 / 1_0000, y1 % 1_0000);
                lower((*p).add(20), b, x3);
                lower((*p).add(24), b, x2);
                let (x1, x0) = (y0 / 1_0000, y0 % 1_0000);
                lower((*p).add(28), b, x1);
                lower((*p).add(32), b, x0);
                *p = (*p).add(36);
            }
        };
    }
    pub fn proconwritebuf_iint<I>(p: &mut *mut u8, b: &[u8; 40000], d: I)
    where
        I: IPrimInt + std::convert::Into<i128>,
    {
        unsafe {
            if d < I::from(0) {
                let u = std::convert::Into::<i128>::into(d).wrapping_neg() as u128;
                **p = b'-';
                *p = (*p).add(1);
                proconwritebuf_uint(p, b, u);
            } else {
                let u = std::convert::Into::<i128>::into(d) as u128;
                proconwritebuf_uint(p, b, u);
            }
        };
    }
    pub fn proconwritebuf_sp(p: &mut *mut u8) {
        *p = unsafe {
            **p = b' ';
            (*p).add(1)
        }
    }
    pub fn proconwritebuf_lf(p: &mut *mut u8) {
        *p = unsafe {
            **p = b'\n';
            (*p).add(1)
        }
    }
    pub fn proconwritebuf_bytes(p: &mut *mut u8, bytes: &[u8]) {
        *p = unsafe {
            let len = bytes.len();
            std::ptr::copy_nonoverlapping(bytes.as_ptr(), *p, len);
            (*p).add(len)
        };
    }
    pub fn proconwritebuf_str(p: &mut *mut u8, s: &str) {
        *p = unsafe {
            let len = s.len();
            std::ptr::copy_nonoverlapping(s.as_ptr(), *p, len);
            (*p).add(len)
        };
    }
    pub fn proconwritebuf_string(p: &mut *mut u8, s: &String) {
        *p = unsafe {
            let len = s.len();
            std::ptr::copy_nonoverlapping(s.as_ptr(), *p, len);
            (*p).add(len)
        };
    }
}

Submission Info

Judge Result