Submission #38161483

---

Source Code Expand

// -*- coding:utf-8-unix -*-
// rustup doc --std --toolchain 1.42.0

#![allow(unused_imports)]
#![allow(unused_macros)]
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 segtree::*;
use std::collections::*;
use std::io::{stderr, stdin, stdout, BufRead, BufReader, BufWriter, Read, Write};
use superslice::Ext;

pub fn solve() {
    //let tins = std::time::Instant::now();
    //let mut durs = Vec::with_capacity(16);
    use fastproconio::*;
    let stdin = std::io::stdin();
    let mut source = ProconIBufIter::new(stdin.lock());
    macro_rules! fread {
        ($t:tt) => {{
            fread_value!(source, $t)
        }};
    }
    macro_rules! finput {($($r:tt)*)=>{finput_inner!{source, $($r)*}};}
    let mut out = std::io::stdout();
    let mut obuf = ProconWriteBuffer::with_capacity(1 << 26);
    //durs.push((tins.elapsed(), String::from("initial")));
    //let mut out = std::io::BufWriter::new(out.lock());
    //let err = std::io::stderr();
    //let mut err = std::io::BufWriter::new(err.lock());
    finput! {
        n: usize,
    }
    let np1 = n + 1;
    let mut seg_bitor = Segtree::<BitOr<u32>>::from_iter(
        &mut [0u32]
            .iter()
            .cloned()
            .chain((0..n).map(|_| 1u32 << (fread!(byte) - b'a')))
            .chain([1u32 << 25].iter().cloned()),
        n + 2,
    );
    let mut seg_descending = Segtree::<BitOr<bool>>::from_iter(
        &mut seg_bitor.get_slice()
            .windows(2)
            .map(|w| unsafe { *w.get_unchecked(0) > *w.get_unchecked(1) }),
        n + 1,
    );
    finput! {
        q: usize,
    }
    //durs.push((tins.elapsed(), String::from("input")));
    for _ in 0..q {
        match fread!(u32) {
            1 => {
                finput! { x: usize, c: byte }
                let curr_bit = 1 << (c - b'a');
                seg_bitor.set(x, curr_bit);
                let prev_bit = seg_bitor.get(x - 1);
                seg_descending.set(x - 1, prev_bit > curr_bit);
                let next_bit = seg_bitor.get(x + 1);
                seg_descending.set(x, curr_bit > next_bit);
            }
            2 => {
                finput! { l: usize, r: usize }
                let cmask = (seg_bitor.get(l).wrapping_neg() << 1) & (seg_bitor.get(r) - 1);
                obuf.bytes(
                    if seg_descending.prod_bool_or(l, r)
                        || (seg_bitor.prod(1, l) & cmask) != 0
                        || (seg_bitor.prod(r + 1, np1) & cmask) != 0
                    {
                        b"No\n"
                    } else {
                        b"Yes\n"
                    },
                );
            }
            _ => break,
        }
    }
    obuf.write_all(&mut out);
    //let _ = std::io::Write::flush(&mut out);
    //durs.push((tins.elapsed(), String::from("output")));
    //for (dur, s) in durs.iter() { eprintln!("{:.6} {}", dur.as_secs_f64(), s); }
    //let _ = writeln!(&mut err, "{}", count);
    //let _ = std::io::Write::flush(&mut err);
}

pub fn main() {
    const USE_THREAD: bool = false;
    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()
    }
}

/// 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 {
    /// 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/>
    /// this macro recieve `Iterator<Item = u8>` input source, except for Bytes/Chars/String read
    /// ProconIBufIter receive `std::io::BufRead` trait. (`std::io::StdinLock`, `std::io::BufReader`, `&[u8]`, etc.)
    #[macro_export]
    macro_rules! finput_inner {
        ($iter:expr) => {};
        ($iter:expr, ) => {};
        ($iter:expr, mut $var:ident : $t:tt $($r:tt)*) => {
            let mut $var = fread_value!($iter, $t);
            finput_inner!{$iter $($r)*}
        };
        ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
            let $var = fread_value!($iter, $t);
            finput_inner!{$iter $($r)*}
        };
    }
    #[macro_export]
    macro_rules! fread_value {
        ($iter:expr, ( $($t:tt),* )) => { ( $(fread_value!($iter, $t)),* ) };
        ($iter:expr, [ $t:tt ; $len:expr ]) => { (0..$len).map(|_| fread_value!($iter, $t)).collect::<Vec<_>>() };
        ($iter:expr, u128) => { $iter.parse_uint::<u128>() };
        ($iter:expr, usize) => { $iter.parse_uint::<usize>() };
        ($iter:expr, usize1) => { $iter.parse_uint::<usize>() - 1 };
        ($iter:expr, u64) => { $iter.parse_uint::<u64>() };
        ($iter:expr, u64_1) => { $iter.parse_uint::<u64>() - 1 };
        ($iter:expr, u32) => { $iter.parse_uint::<u32>() };
        ($iter:expr, u32_1) => { $iter.parse_uint::<u32>() - 1 };
        ($iter:expr, u16) => { $iter.parse_uint::<u16>() };
        ($iter:expr, u8) => { $iter.parse_uint::<u8>() };
        ($iter:expr, i128) => { $iter.parse_iint::<i128>() };
        ($iter:expr, isize) => { $iter.parse_iint::<isize>() };
        ($iter:expr, i64) => { $iter.parse_iint::<i64>() };
        ($iter:expr, i32) => { $iter.parse_iint::<i32>() };
        ($iter:expr, i16) => { $iter.parse_iint::<i16>() };
        ($iter:expr, i8) => { $iter.parse_iint::<i16>() as i8 };
        ($iter:expr, byte) => { $iter.get_ascii_byte() };
        ($iter:expr, Bytes) => {{ let mut v = vec![];$iter.get_ascii_bytes(&mut v);v }};
        ($iter:expr, Chars) => {{ let mut v = vec![];$iter.get_ascii_chars(&mut v);v }};
        ($iter:expr, String) => {{ let mut v = vec![];$iter.get_ascii_bytes(&mut v);unsafe { std::string::String::from_utf8_unchecked(v) }}};
        ($iter:expr, LineBytes) => {{ let mut v = vec![];$iter.get_ascii_line_bytes(&mut v).and(Some(v)).unwrap() }};
        ($iter:expr, LineBytesTrim) => {{ let mut v = vec![];$iter.get_ascii_line_bytes_trim(&mut v);v }};
        ($iter:expr, LineString) => {{ let mut v = vec![];$iter.get_ascii_line_bytes(&mut v);unsafe { std::string::String::from_utf8_unchecked(v) }}};
        ($iter:expr, LineStringTrim) => {{ let mut v = vec![];$iter.get_ascii_line_bytes_trim(&mut v);unsafe { std::string::String::from_utf8_unchecked(v) }}};
        ($iter:expr, Utf8Bytes) => {{ let mut v = vec![];$iter.get_utf8_bytes(&mut v);v }};
        ($iter:expr, Utf8String) => {{ let mut v = vec![];$iter.get_utf8_bytes(&mut v);unsafe { std::string::String::from_utf8_unchecked(v) }}};
        ($iter:expr, Utf8LineBytes) => {{ let mut v = vec![];$iter.get_utf8_line_bytes(&mut v);v }};
        ($iter:expr, Utf8LineBytesTrim) => {{ let mut v = vec![];$iter.get_utf8_line_bytes_trim(&mut v);v }};
        ($iter:expr, Utf8LineString) => {{ let mut v = vec![];$iter.get_utf8_line_bytes(&mut v);unsafe { std::string::String::from_utf8_unchecked(v) }}};
        ($iter:expr, Utf8LineStringTrim) => {{ let mut v = vec![];$iter.get_utf8_line_bytes_trim(&mut v);unsafe { std::string::String::from_utf8_unchecked(v) }}};
        ($iter:expr, $t:ty) => {{ let mut v = vec![];unsafe { std::string::String::from_utf8_unchecked($iter.get_utf8_bytes(&mut v).and(Some(v)).unwrap()) }.parse::<$t>().expect("Parse error") }};
    }

    /// Interaction with `std::io::BufRead` Trait, Implementation of `Iterator<Item = u8>`
    pub struct ProconIBufIter<R: std::io::BufRead> {
        inner: R,
        raw: *const u8,
        len: usize,
        ptr: *const u8,
        end: *const u8,
    }
    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
    }
    impl<R: std::io::BufRead> ProconIBufIter<R> {
        /// consume raw buffer
        #[allow(unused)]
        fn consume(&mut self, amt: usize) {
            let remain = unsafe { ptr_offset_u8(self.end, self.ptr) };
            assert!(remain >= amt);
            unsafe {
                self.ptr = self.ptr.add(amt);
            }
        }
        /// read when buffer is empty
        unsafe fn inner_read(&mut self) -> bool {
            assert!(self.is_empty());
            self.inner.consume(self.len);
            let buffer = self.inner.fill_buf().unwrap();
            let raw = buffer.as_ptr();
            let len = buffer.len();
            self.raw = raw;
            self.len = len;
            self.ptr = raw;
            self.end = raw.add(len);
            self.len > 0
        }
        /// check end of buffer
        fn is_empty(&self) -> bool {
            self.ptr == self.end
        }
        /// Interaction with `std::io::BufRead` Trait, Implementation of `Iterator<Item = u8>`
        pub fn new(inner: R) -> Self {
            let mut bufiter = Self {
                inner,
                raw: std::ptr::null(),
                len: 0,
                ptr: std::ptr::null(),
                end: std::ptr::null(),
            };
            unsafe { bufiter.inner_read() };
            bufiter
        }
        /// next(), but return empty value
        #[allow(unused)]
        fn next_unread(&mut self) -> Option<()> {
            if self.is_empty() && unsafe { !self.inner_read() } {
                return None;
            }
            unsafe {
                self.ptr = self.ptr.add(1);
            }
            return Some(());
        }
        /// get now pointer & increment pointer
        unsafe fn next_unchecked(&mut self) -> u8 {
            let p = self.ptr;
            self.ptr = p.add(1);
            *p
        }
        /// peek
        #[allow(unused)]
        fn peek(&mut self) -> Option<&u8> {
            if !self.is_empty() || unsafe { self.inner_read() } {
                unsafe { Some(&*self.ptr) }
            } else {
                None
            }
        }
        /// raw buffer
        #[allow(unused)]
        fn raw_buf(&mut self) -> &[u8] {
            if self.is_empty() {
                unsafe {
                    self.inner_read();
                }
            }
            unsafe { std::slice::from_raw_parts(self.ptr, ptr_offset_u8(self.end, self.ptr)) }
        }
        /// 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;
                }
            }
        }
    }
    impl<R: std::io::BufRead> Iterator for ProconIBufIter<R> {
        type Item = u8;
        /// fetch next byte
        fn next(&mut self) -> Option<Self::Item> {
            if !self.is_empty() || unsafe { self.inner_read() } {
                unsafe { Some(self.next_unchecked()) }
            } else {
                None
            }
        }
        /// remain size hint
        fn size_hint(&self) -> (usize, Option<usize>) {
            (unsafe { ptr_offset_u8(self.end, self.ptr) }, 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) });
        }
    }
    /// speed frenzy input parser for program compete (fail parse may cause undefined behavior)
    pub trait ProconParse {
        /// parse unsigned integer
        fn parse_uint<
            U: Copy
                + std::cmp::Ord
                + std::ops::BitAnd<Output = U>
                + std::ops::Add<Output = U>
                + std::ops::Sub<Output = U>
                + std::ops::Mul<Output = U>
                + std::convert::From<u8>,
        >(
            &mut self,
        ) -> U;
        /// parse signed integer
        fn parse_iint<
            I: Copy
                + std::cmp::Ord
                + std::ops::BitAnd<Output = I>
                + std::ops::Add<Output = I>
                + std::ops::Sub<Output = I>
                + std::ops::Mul<Output = I>
                + std::convert::From<u8>
                + std::ops::Neg<Output = I>,
        >(
            &mut self,
        ) -> I;
        /// get char (printable ascii char)
        fn parse_byte(&mut self) -> u8;
        /// get chars (printable ascii word)
        fn parse_bytes(&mut self) -> Vec<u8>;
        /// get line chars (sp+printable ascii)
        fn parse_line_bytes(&mut self) -> Vec<u8>;
        /// get line chars (trimed sp+printable ascii)
        fn parse_line_bytes_trim(&mut self) -> Vec<u8>;
    }
    /// speed frenzy input byte reader for program compete
    pub trait ProconBytes {
        /// get bytes
        fn get_bytes_fn<F: Fn(u8) -> bool>(&mut self, vec: &mut Vec<u8>, f: &mut F);
        /// get chars
        fn get_ascii_chars_fn<F: Fn(u8) -> bool>(&mut self, vec: &mut Vec<char>, f: &mut F);
        /// get byte (printable ascii char)
        fn get_ascii_byte(&mut self) -> u8;
        /// get bytes (printable ascii word)
        fn get_ascii_bytes(&mut self, vec: &mut Vec<u8>);
        /// get chars (printable ascii word)
        fn get_ascii_chars(&mut self, vec: &mut Vec<char>);
        /// get line bytes (sp+printable ascii)
        fn get_ascii_line_bytes(&mut self, vec: &mut Vec<u8>);
        /// get line bytes (trimed sp+printable ascii)
        fn get_ascii_line_bytes_trim(&mut self, vec: &mut Vec<u8>);
        /// get bytes (printable utf8 word)
        fn get_utf8_bytes(&mut self, vec: &mut Vec<u8>);
        /// get line bytes (sp+printable utf8)
        fn get_utf8_line_bytes(&mut self, vec: &mut Vec<u8>);
        /// get line bytes (trimed sp+printable utf8)
        fn get_utf8_line_bytes_trim(&mut self, vec: &mut Vec<u8>);
    }
    impl<T: Iterator<Item = u8>> ProconParse for T {
        fn parse_uint<
            U: Copy
                + std::cmp::Ord
                + std::ops::BitAnd<Output = U>
                + std::ops::Add<Output = U>
                + std::ops::Sub<Output = U>
                + std::ops::Mul<Output = U>
                + std::convert::From<u8>,
        >(
            &mut self,
        ) -> U {
            loop {
                match self.next() {
                    Some(c @ b'0'..=b'9') => {
                        let mut x = U::from(c.wrapping_sub(b'0'));
                        while let Some(c @ b'0'..=b'9') = self.next() {
                            x = x.mul(U::from(10)).add(U::from(c.wrapping_sub(b'0')));
                        }
                        break x;
                    }
                    Some(_) => continue,
                    None => unreachable!(),
                }
            }
        }
        fn parse_iint<
            I: Copy
                + std::cmp::Ord
                + std::ops::BitAnd<Output = I>
                + std::ops::Add<Output = I>
                + std::ops::Sub<Output = I>
                + std::ops::Mul<Output = I>
                + std::ops::Neg<Output = I>
                + std::convert::From<u8>,
        >(
            &mut self,
        ) -> I {
            loop {
                match self.next() {
                    Some(c @ b'0'..=b'9') => {
                        let mut x = I::from(c.wrapping_sub(b'0'));
                        while let Some(c @ b'0'..=b'9') = self.next() {
                            x = x.mul(I::from(10)).add(I::from(c.wrapping_sub(b'0')));
                        }
                        break x;
                    }
                    Some(b'-') => {
                        let mut x = if let Some(c @ b'0'..=b'9') = self.next() {
                            I::from(c.wrapping_sub(b'0')).neg()
                        } else {
                            unreachable!();
                        };
                        while let Some(c @ b'0'..=b'9') = self.next() {
                            x = x.mul(I::from(10)).sub(I::from(c.wrapping_sub(b'0')));
                        }
                        break x;
                    }
                    Some(_) => continue,
                    None => unreachable!(),
                }
            }
        }
        fn parse_byte(&mut self) -> u8 {
            loop {
                match self.next() {
                    Some(c @ b'!'..=b'~') => break c,
                    Some(_) => continue,
                    None => break b'\0',
                }
            }
        }
        fn parse_bytes(&mut self) -> Vec<u8> {
            let mut v = vec![];
            loop {
                match self.next() {
                    Some(c @ b'!'..=b'~') => {
                        v.push(c);
                        while let Some(c @ b'!'..=b'~') = self.next() {
                            v.push(c);
                        }
                        break v;
                    }
                    Some(_) => continue,
                    None => break v,
                }
            }
        }
        fn parse_line_bytes(&mut self) -> Vec<u8> {
            let mut v = vec![];
            loop {
                match self.next() {
                    Some(c @ b' '..=b'~') => {
                        v.push(c);
                        while let Some(c @ b' '..=b'~') = self.next() {
                            v.push(c);
                        }
                        break v;
                    }
                    Some(_) => continue,
                    None => break v,
                }
            }
        }
        fn parse_line_bytes_trim(&mut self) -> Vec<u8> {
            let mut v = vec![];
            loop {
                match self.next() {
                    Some(c @ b'!'..=b'~') => {
                        v.push(c);
                        while let Some(c @ b' '..=b'~') = self.next() {
                            v.push(c);
                        }
                        while v.last() == Some(&b' ') {
                            v.pop();
                        }
                        break v;
                    }
                    Some(_) => continue,
                    None => break v,
                }
            }
        }
    }
    impl<R: std::io::BufRead> ProconBytes for ProconIBufIter<R> {
        /// get bytes vector
        fn get_bytes_fn<F: Fn(u8) -> bool>(&mut self, vec: &mut Vec<u8>, f: &mut F) {
            if !self.skipuntil_bytes_fn(f) {
                return;
            }
            let begin_ptr = self.ptr;
            let mut ptr = self.ptr;
            loop {
                unsafe {
                    ptr = ptr.add(1);
                }
                if ptr == self.end {
                    self.ptr = ptr;
                    vec.extend_from_slice(unsafe {
                        std::slice::from_raw_parts(begin_ptr, ptr_offset_u8(ptr, begin_ptr))
                    });
                    break;
                }
                if !f(unsafe { *ptr }) {
                    self.ptr = ptr;
                    vec.extend_from_slice(unsafe {
                        std::slice::from_raw_parts(begin_ptr, ptr_offset_u8(ptr, begin_ptr))
                    });
                    return;
                }
            }
            if unsafe { !self.inner_read() } {
                return;
            }
            ptr = self.ptr;
            loop {
                if !f(unsafe { *ptr }) {
                    self.ptr = ptr;
                    vec.extend_from_slice(unsafe {
                        std::slice::from_raw_parts(self.raw, ptr_offset_u8(ptr, self.raw))
                    });
                    return;
                }
                unsafe {
                    ptr = ptr.add(1);
                }
                if ptr == self.end {
                    self.ptr = ptr;
                    vec.extend_from_slice(unsafe {
                        std::slice::from_raw_parts(self.raw, self.len)
                    });
                    if unsafe { !self.inner_read() } {
                        return;
                    }
                    ptr = self.ptr;
                }
            }
        }
        fn get_ascii_chars_fn<F: Fn(u8) -> bool>(&mut self, vec: &mut Vec<char>, f: &mut F) {
            if !self.skipuntil_bytes_fn(f) {
                return;
            }
            let begin_ptr = self.ptr;
            let mut ptr = self.ptr;
            loop {
                unsafe {
                    ptr = ptr.add(1);
                }
                if ptr == self.end {
                    self.ptr = ptr;
                    let len = unsafe { ptr_offset_u8(ptr, begin_ptr) };
                    vec.reserve(len);
                    let mut p = begin_ptr;
                    while p != ptr {
                        vec.push(unsafe { *p } as char);
                        p = unsafe { p.add(1) };
                    }
                    break;
                }
                if !f(unsafe { *ptr }) {
                    self.ptr = ptr;
                    let len = unsafe { ptr_offset_u8(ptr, begin_ptr) };
                    vec.reserve(len);
                    let mut p = begin_ptr;
                    while p != ptr {
                        vec.push(unsafe { *p } as char);
                        p = unsafe { p.add(1) };
                    }
                    return;
                }
            }
            if unsafe { !self.inner_read() } {
                return;
            }
            ptr = self.ptr;
            loop {
                if !f(unsafe { *ptr }) {
                    self.ptr = ptr;
                    let len = unsafe { ptr_offset_u8(ptr, self.raw) };
                    vec.reserve(len);
                    let mut p = self.raw;
                    while p != ptr {
                        vec.push(unsafe { *p } as char);
                        p = unsafe { p.add(1) };
                    }
                    return;
                }
                unsafe {
                    ptr = ptr.add(1);
                }
                if ptr == self.end {
                    self.ptr = ptr;
                    let len = unsafe { ptr_offset_u8(ptr, self.raw) };
                    vec.reserve(len);
                    let mut p = self.raw;
                    while p != ptr {
                        vec.push(unsafe { *p } as char);
                        p = unsafe { p.add(1) };
                    }
                    if unsafe { !self.inner_read() } {
                        return;
                    }
                    ptr = self.ptr;
                }
            }
        }
        fn get_ascii_byte(&mut self) -> u8 {
            loop {
                match self.next() {
                    Some(c @ b'!'..=b'~') => break c,
                    Some(_) => continue,
                    None => break b'\0',
                }
            }
        }
        fn get_ascii_bytes(&mut self, vec: &mut Vec<u8>) {
            self.get_bytes_fn(vec, &mut |c| (b'!'..=b'~').contains(&c))
        }
        fn get_ascii_chars(&mut self, vec: &mut Vec<char>) {
            self.get_ascii_chars_fn(vec, &mut |c| (b'!'..=b'~').contains(&c))
        }
        fn get_ascii_line_bytes(&mut self, vec: &mut Vec<u8>) {
            self.get_bytes_fn(vec, &mut |c| (b' '..=b'~').contains(&c))
        }
        fn get_ascii_line_bytes_trim(&mut self, vec: &mut Vec<u8>) {
            self.skipuntil_bytes_fn(&mut |c| (b'!'..=b'~').contains(&c));
            self.get_bytes_fn(vec, &mut |c| (b' '..=b'~').contains(&c));
            while vec.last() == Some(&b' ') {
                vec.pop();
            }
        }
        fn get_utf8_bytes(&mut self, vec: &mut Vec<u8>) {
            self.get_bytes_fn(vec, &mut |c| (b'!'..=0xf4).contains(&c))
        }
        fn get_utf8_line_bytes(&mut self, vec: &mut Vec<u8>) {
            self.get_bytes_fn(vec, &mut |c| (b' '..=0xf4).contains(&c))
        }
        fn get_utf8_line_bytes_trim(&mut self, vec: &mut Vec<u8>) {
            self.skipuntil_bytes_fn(&mut |c| (b'!'..=0xf4).contains(&c));
            self.get_bytes_fn(vec, &mut |c| (b' '..=0xf4).contains(&c));
            while vec.last() == Some(&b' ') {
                vec.pop();
            }
        }
    }
    /// Insufficient write buffer size causes undefined operation.
    pub struct ProconWriteBuffer(*mut u8, Vec<u8>);
    impl ProconWriteBuffer {
        pub fn with_capacity(capacity: usize) -> Self {
            let mut b = Vec::<u8>::with_capacity(capacity);
            let ptr = b.as_mut_ptr();
            Self(ptr, b)
        }
        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 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: Copy
                + std::cmp::Ord
                + std::ops::Div<Output = U>
                + std::ops::Rem<Output = U>
                + std::convert::From<u8>
                + std::convert::Into<u128>,
        {
            proconwritebuf_uint(&mut self.0, d);
        }
        pub fn uint_sp<U>(&mut self, s: &[U])
        where
            U: Copy
                + std::cmp::Ord
                + std::ops::Div<Output = U>
                + std::ops::Rem<Output = U>
                + std::convert::From<u8>
                + std::convert::Into<u128>,
        {
            let mut p = self.0;
            let mut it = s.iter();
            if let Some(&d) = it.next() {
                proconwritebuf_uint(&mut p, d);
                for &d in it {
                    proconwritebuf_sp(&mut p);
                    proconwritebuf_uint(&mut p, d);
                }
            }
            self.0 = p;
        }
        pub fn uint_splf<U>(&mut self, s: &[U])
        where
            U: Copy
                + std::cmp::Ord
                + std::ops::Div<Output = U>
                + std::ops::Rem<Output = U>
                + std::convert::From<u8>
                + std::convert::Into<u128>,
        {
            let mut p = self.0;
            let mut it = s.iter();
            if let Some(&d) = it.next() {
                proconwritebuf_uint(&mut p, d);
                for &d in it {
                    proconwritebuf_sp(&mut p);
                    proconwritebuf_uint(&mut p, d);
                }
            }
            proconwritebuf_lf(&mut p);
            self.0 = p;
        }
        pub fn usize(&mut self, d: usize) {
            proconwritebuf_uint(&mut self.0, 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, d as u64);
                for &d in it {
                    proconwritebuf_sp(&mut p);
                    proconwritebuf_uint(&mut p, 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, d as u64);
                for &d in it {
                    proconwritebuf_sp(&mut p);
                    proconwritebuf_uint(&mut p, d as u64);
                }
            }
            proconwritebuf_lf(&mut p);
            self.0 = p;
        }
        pub fn iint<I>(&mut self, d: I)
        where
            I: Copy
                + std::cmp::Ord
                + std::ops::Neg<Output = I>
                + std::ops::Div<Output = I>
                + std::ops::Rem<Output = I>
                + std::convert::From<i8>
                + std::convert::Into<i128>,
        {
            proconwritebuf_iint(&mut self.0, d);
        }
        pub fn iint_sp<I>(&mut self, s: &[I])
        where
            I: Copy
                + std::cmp::Ord
                + std::ops::Neg<Output = I>
                + std::ops::Div<Output = I>
                + std::ops::Rem<Output = I>
                + std::convert::From<i8>
                + std::convert::Into<i128>,
        {
            let mut p = self.0;
            let mut it = s.iter();
            if let Some(&d) = it.next() {
                proconwritebuf_iint(&mut p, d);
                for &d in it {
                    proconwritebuf_sp(&mut p);
                    proconwritebuf_iint(&mut p, d);
                }
            }
            self.0 = p;
        }
        pub fn iint_splf<I>(&mut self, s: &[I])
        where
            I: Copy
                + std::cmp::Ord
                + std::ops::Neg<Output = I>
                + std::ops::Div<Output = I>
                + std::ops::Rem<Output = I>
                + std::convert::From<i8>
                + 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, d);
                for &d in it {
                    proconwritebuf_sp(&mut p);
                    proconwritebuf_iint(&mut p, 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, mut d: U)
    where
        U: Copy
            + std::cmp::Ord
            + std::ops::Div<Output = U>
            + std::ops::Rem<Output = U>
            + std::convert::From<u8>
            + std::convert::Into<u128>,
    {
        unsafe {
            let bptr = *p;
            let mut cptr = bptr;
            if d != U::from(0) {
                while d != U::from(0) {
                    let (q, r) = (d / U::from(10), d % U::from(10));
                    d = q;
                    *cptr = b'0' + U::into(r) as u8;
                    cptr = cptr.add(1);
                }
                *p = cptr;
                let mut lptr = bptr;
                let mut rptr = cptr.sub(1);
                while (lptr as usize) < (rptr as usize) {
                    let (dr, dl) = (*lptr, *rptr);
                    *lptr = dl;
                    *rptr = dr;
                    lptr = lptr.add(1);
                    rptr = rptr.sub(1);
                }
            } else {
                *cptr = b'0';
                *p = cptr.add(1);
            }
        };
    }
    pub fn proconwritebuf_iint<I>(p: &mut *mut u8, mut d: I)
    where
        I: Copy
            + std::cmp::Ord
            + std::ops::Neg<Output = I>
            + std::ops::Div<Output = I>
            + std::ops::Rem<Output = I>
            + std::convert::From<i8>
            + std::convert::Into<i128>,
    {
        unsafe {
            let bptr = *p;
            let mut cptr = bptr;
            if d > I::from(0) {
                while d != I::from(0) {
                    let (q, r) = (d / I::from(10), d % I::from(10));
                    d = q;
                    *cptr = b'0' + I::into(r) as u8;
                    cptr = cptr.add(1);
                }
                *p = cptr;
                let mut lptr = bptr;
                let mut rptr = cptr.sub(1);
                while (lptr as usize) < (rptr as usize) {
                    let (dr, dl) = (*lptr, *rptr);
                    *lptr = dl;
                    *rptr = dr;
                    lptr = lptr.add(1);
                    rptr = rptr.sub(1);
                }
            } else if d < I::from(0) {
                *cptr = b'-';
                cptr = cptr.add(1);
                let mptr = cptr;
                {
                    let (q, r) = (-(d / I::from(10)), -(d % I::from(10)));
                    d = q;
                    *cptr = b'0' + I::into(r) as u8;
                    cptr = cptr.add(1);
                }
                while d != I::from(0) {
                    let (q, r) = (d / I::from(10), d % I::from(10));
                    d = q;
                    *cptr = b'0' + I::into(r) as u8;
                    cptr = cptr.add(1);
                }
                *p = cptr;
                let mut lptr = mptr;
                let mut rptr = cptr.sub(1);
                while (lptr as usize) < (rptr as usize) {
                    let (dr, dl) = (*lptr, *rptr);
                    *lptr = dl;
                    *rptr = dr;
                    lptr = lptr.add(1);
                    rptr = rptr.sub(1);
                }
            } else {
                *cptr = b'0';
                *p = cptr.add(1);
            }
        };
    }
    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)
        };
    }
}
//https://github.com/rust-lang-ja/ac-library-rs

pub mod internal_bit {
    // Skipped:
    //
    // - `bsf` = `__builtin_ctz`: is equivalent to `{integer}::trailing_zeros`

    #[allow(dead_code)]
    pub(crate) fn ceil_pow2(n: u32) -> u32 {
        32 - n.saturating_sub(1).leading_zeros()
    }

    #[cfg(test)]
    mod tests {
        #[test]
        fn ceil_pow2() {
            // https://github.com/atcoder/ac-library/blob/2088c8e2431c3f4d29a2cfabc6529fe0a0586c48/test/unittest/bit_test.cpp
            assert_eq!(0, super::ceil_pow2(0));
            assert_eq!(0, super::ceil_pow2(1));
            assert_eq!(1, super::ceil_pow2(2));
            assert_eq!(2, super::ceil_pow2(3));
            assert_eq!(2, super::ceil_pow2(4));
            assert_eq!(3, super::ceil_pow2(5));
            assert_eq!(3, super::ceil_pow2(6));
            assert_eq!(3, super::ceil_pow2(7));
            assert_eq!(3, super::ceil_pow2(8));
            assert_eq!(4, super::ceil_pow2(9));
            assert_eq!(30, super::ceil_pow2(1 << 30));
            assert_eq!(31, super::ceil_pow2((1 << 30) + 1));

            assert_eq!(32, super::ceil_pow2(u32::max_value()));
        }
    }
}
pub mod internal_type_traits {
    use std::{
        fmt,
        iter::{Product, Sum},
        ops::{
            Add, AddAssign, BitAnd, BitAndAssign, BitOr, BitOrAssign, BitXor, BitXorAssign, Div,
            DivAssign, Mul, MulAssign, Not, Rem, RemAssign, Shl, ShlAssign, Shr, ShrAssign, Sub,
            SubAssign,
        },
    };

    // Skipped:
    //
    // - `is_signed_int_t<T>`   (probably won't be used directly in `modint.rs`)
    // - `is_unsigned_int_t<T>` (probably won't be used directly in `modint.rs`)
    // - `to_unsigned_t<T>`     (not used in `fenwicktree.rs`)

    /// Corresponds to `std::is_integral` in C++.
    // We will remove unnecessary bounds later.
    //
    // Maybe we should rename this to `PrimitiveInteger` or something, as it probably won't be used in the
    // same way as the original ACL.
    pub trait Integral:
        'static
        + Send
        + Sync
        + Copy
        + Ord
        + Not<Output = Self>
        + Add<Output = Self>
        + Sub<Output = Self>
        + Mul<Output = Self>
        + Div<Output = Self>
        + Rem<Output = Self>
        + AddAssign
        + SubAssign
        + MulAssign
        + DivAssign
        + RemAssign
        + Sum
        + Product
        + BitOr<Output = Self>
        + BitAnd<Output = Self>
        + BitXor<Output = Self>
        + BitOrAssign
        + BitAndAssign
        + BitXorAssign
        + Shl<Output = Self>
        + Shr<Output = Self>
        + ShlAssign
        + ShrAssign
        + fmt::Display
        + fmt::Debug
        + fmt::Binary
        + fmt::Octal
        + Zero
        + One
        + BoundedBelow
        + BoundedAbove
    {
    }

    /// Class that has additive identity element
    pub trait Zero {
        /// The additive identity element
        fn zero() -> Self;
    }

    /// Class that has multiplicative identity element
    pub trait One {
        /// The multiplicative identity element
        fn one() -> Self;
    }

    pub trait BoundedBelow {
        fn min_value() -> Self;
    }

    pub trait BoundedAbove {
        fn max_value() -> Self;
    }

    macro_rules! impl_integral {
    ($($ty:ty),*) => {
        $(
            impl Zero for $ty {
                #[inline]
                fn zero() -> Self {
                    0
                }
            }

            impl One for $ty {
                #[inline]
                fn one() -> Self {
                    1
                }
            }

            impl BoundedBelow for $ty {
                #[inline]
                fn min_value() -> Self {
                    Self::min_value()
                }
            }

            impl BoundedAbove for $ty {
                #[inline]
                fn max_value() -> Self {
                    Self::max_value()
                }
            }

            impl Integral for $ty {}
        )*
    };
}

    impl_integral!(i8, i16, i32, i64, i128, isize, u8, u16, u32, u64, u128, usize);
}
pub mod segtree {
    use crate::internal_bit::ceil_pow2;
    use crate::internal_type_traits::{BoundedAbove, BoundedBelow, One, Zero};
    use std::cmp::{max, min};
    use std::convert::Infallible;
    use std::marker::PhantomData;
    use std::ops::{Add, Mul};

    // TODO Should I split monoid-related traits to another module?
    pub trait Monoid {
        type S: Clone;
        fn identity() -> Self::S;
        fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S;
    }

    pub struct Max<S>(Infallible, PhantomData<fn() -> S>);
    impl<S> Monoid for Max<S>
    where
        S: Copy + Ord + BoundedBelow,
    {
        type S = S;
        fn identity() -> Self::S {
            S::min_value()
        }
        fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S {
            max(*a, *b)
        }
    }

    pub struct Min<S>(Infallible, PhantomData<fn() -> S>);
    impl<S> Monoid for Min<S>
    where
        S: Copy + Ord + BoundedAbove,
    {
        type S = S;
        fn identity() -> Self::S {
            S::max_value()
        }
        fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S {
            min(*a, *b)
        }
    }

    pub struct BitOr<S>(Infallible, PhantomData<fn() -> S>);
    impl<S> Monoid for BitOr<S>
    where
        S: Copy + std::ops::BitOr<Output = S> + Default,
    {
        type S = S;
        fn identity() -> Self::S {
            S::default()
        }
        fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S {
            *a | *b
        }
    }

    pub struct BitAnd<S>(Infallible, PhantomData<fn() -> S>);
    impl<S> Monoid for BitAnd<S>
    where
        S: Copy + std::ops::BitAnd<Output = S> + std::ops::Not<Output = S> + Default,
    {
        type S = S;
        fn identity() -> Self::S {
            !S::default()
        }
        fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S {
            *a & *b
        }
    }

    pub struct BitXor<S>(Infallible, PhantomData<fn() -> S>);
    impl<S> Monoid for BitXor<S>
    where
        S: Copy + std::ops::BitXor<Output = S> + Default,
    {
        type S = S;
        fn identity() -> Self::S {
            S::default()
        }
        fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S {
            *a ^ *b
        }
    }

    pub struct Additive<S>(Infallible, PhantomData<fn() -> S>);
    impl<S> Monoid for Additive<S>
    where
        S: Copy + Add<Output = S> + Zero,
    {
        type S = S;
        fn identity() -> Self::S {
            S::zero()
        }
        fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S {
            *a + *b
        }
    }

    pub struct Multiplicative<S>(Infallible, PhantomData<fn() -> S>);
    impl<S> Monoid for Multiplicative<S>
    where
        S: Copy + Mul<Output = S> + One,
    {
        type S = S;
        fn identity() -> Self::S {
            S::one()
        }
        fn binary_operation(a: &Self::S, b: &Self::S) -> Self::S {
            *a * *b
        }
    }

    impl<M: Monoid> Default for Segtree<M> {
        fn default() -> Self {
            Segtree::new(0)
        }
    }
    impl<M: Monoid> Segtree<M> {
        pub fn new(n: usize) -> Segtree<M> {
            vec![M::identity(); n].into()
        }
    }
    impl<M: Monoid> Segtree<M> {
        pub fn from_iter<I: Iterator<Item = M::S>>(it: &mut I, n: usize) -> Self {
            let log = ceil_pow2(n as u32) as usize;
            let size = 1 << log;
            let mut d = vec![M::identity(); 2 * size];
            for (se, de) in it.zip(d[size..(size + n)].iter_mut()) {
                *de = se;
            }
            let mut ret = Segtree { n, size, log, d };
            for i in (1..size).rev() {
                ret.update(i);
            }
            ret
        }
    }
    impl<M: Monoid> From<Vec<M::S>> for Segtree<M> {
        fn from(v: Vec<M::S>) -> Self {
            let n = v.len();
            let log = ceil_pow2(n as u32) as usize;
            let size = 1 << log;
            let mut d = vec![M::identity(); 2 * size];
            d[size..(size + n)].clone_from_slice(&v);
            let mut ret = Segtree { n, size, log, d };
            for i in (1..size).rev() {
                ret.update(i);
            }
            ret
        }
    }
    impl<M> Segtree<M>
    where
        M: Monoid,
        M::S: Copy + std::convert::Into<bool>,
    {
        pub fn prod_bool_or(&self, mut l: usize, mut r: usize) -> M::S {
            debug_assert!(l <= r && r <= self.n);
            l += self.size;
            r += self.size;

            while l < r {
                if l & 1 != 0 {
                    let te = unsafe { *self.d.get_unchecked(l) };
                    if te.into() {
                        return te;
                    }
                    l += 1;
                }
                if r & 1 != 0 {
                    r -= 1;
                    let te = unsafe { *self.d.get_unchecked(r) };
                    if te.into() {
                        return te;
                    }
                }
                l >>= 1;
                r >>= 1;
            }

            M::identity()
        }
    }
    impl<M: Monoid> Segtree<M> {
        pub fn set(&mut self, mut p: usize, x: M::S) {
            debug_assert!(p < self.n);
            p += self.size;
            unsafe { *self.d.get_unchecked_mut(p) = x };
            for i in 1..=self.log {
                self.update(p >> i);
            }
        }

        pub fn get(&self, p: usize) -> M::S {
            debug_assert!(p < self.n);
            unsafe { self.d.get_unchecked(p + self.size).clone() }
        }

        pub fn get_slice(&self) -> &[M::S] {
            &self.d[self.size..(self.size + self.n)]
        }

        pub fn prod(&self, mut l: usize, mut r: usize) -> M::S {
            debug_assert!(l <= r && r <= self.n);
            let mut sml = M::identity();
            let mut smr = M::identity();
            l += self.size;
            r += self.size;

            while l < r {
                if l & 1 != 0 {
                    sml = M::binary_operation(&sml, unsafe { self.d.get_unchecked(l) });
                    l += 1;
                }
                if r & 1 != 0 {
                    r -= 1;
                    smr = M::binary_operation(unsafe { self.d.get_unchecked(r) }, &smr);
                }
                l >>= 1;
                r >>= 1;
            }

            M::binary_operation(&sml, &smr)
        }

        pub fn all_prod(&self) -> M::S {
            self.d[1].clone()
        }

        pub fn max_right<F>(&self, mut l: usize, f: F) -> usize
        where
            F: Fn(&M::S) -> bool,
        {
            debug_assert!(l <= self.n);
            debug_assert!(f(&M::identity()));
            if l == self.n {
                return self.n;
            }
            l += self.size;
            let mut sm = M::identity();
            while {
                // do
                while l % 2 == 0 {
                    l >>= 1;
                }
                if !f(&M::binary_operation(&sm, &self.d[l])) {
                    while l < self.size {
                        l *= 2;
                        let res = M::binary_operation(&sm, &self.d[l]);
                        if f(&res) {
                            sm = res;
                            l += 1;
                        }
                    }
                    return l - self.size;
                }
                sm = M::binary_operation(&sm, &self.d[l]);
                l += 1;
                // while
                {
                    let l = l as isize;
                    (l & -l) != l
                }
            } {}
            self.n
        }

        pub fn min_left<F>(&self, mut r: usize, f: F) -> usize
        where
            F: Fn(&M::S) -> bool,
        {
            debug_assert!(r <= self.n);
            debug_assert!(f(&M::identity()));
            if r == 0 {
                return 0;
            }
            r += self.size;
            let mut sm = M::identity();
            while {
                // do
                r -= 1;
                while r > 1 && r % 2 == 1 {
                    r >>= 1;
                }
                if !f(&M::binary_operation(&self.d[r], &sm)) {
                    while r < self.size {
                        r = 2 * r + 1;
                        let res = M::binary_operation(&self.d[r], &sm);
                        if f(&res) {
                            sm = res;
                            r -= 1;
                        }
                    }
                    return r + 1 - self.size;
                }
                sm = M::binary_operation(&self.d[r], &sm);
                // while
                {
                    let r = r as isize;
                    (r & -r) != r
                }
            } {}
            0
        }

        fn update(&mut self, k: usize) {
            unsafe {
                *self.d.get_unchecked_mut(k) = M::binary_operation(
                    self.d.get_unchecked(2 * k),
                    self.d.get_unchecked(2 * k + 1),
                );
            }
        }
    }

    // Maybe we can use this someday
    // ```
    // for i in 0..=self.log {
    //     for j in 0..1 << i {
    //         print!("{}\t", self.d[(1 << i) + j]);
    //     }
    //     println!();
    // }
    // ```

    pub struct Segtree<M>
    where
        M: Monoid,
    {
        // variable name is _n in original library
        n: usize,
        size: usize,
        log: usize,
        d: Vec<M::S>,
    }

    #[cfg(test)]
    mod tests {
        use crate::segtree::Max;
        use crate::Segtree;

        #[test]
        fn test_max_segtree() {
            let base = vec![3, 1, 4, 1, 5, 9, 2, 6, 5, 3];
            let n = base.len();
            let segtree: Segtree<Max<_>> = base.clone().into();
            check_segtree(&base, &segtree);

            let mut segtree = Segtree::<Max<_>>::new(n);
            let mut internal = vec![i32::min_value(); n];
            for i in 0..n {
                segtree.set(i, base[i]);
                internal[i] = base[i];
                check_segtree(&internal, &segtree);
            }

            segtree.set(6, 5);
            internal[6] = 5;
            check_segtree(&internal, &segtree);

            segtree.set(6, 0);
            internal[6] = 0;
            check_segtree(&internal, &segtree);
        }

        //noinspection DuplicatedCode
        fn check_segtree(base: &[i32], segtree: &Segtree<Max<i32>>) {
            let n = base.len();
            #[allow(clippy::needless_range_loop)]
            for i in 0..n {
                assert_eq!(segtree.get(i), base[i]);
            }
            for i in 0..=n {
                for j in i..=n {
                    assert_eq!(
                        segtree.prod(i, j),
                        base[i..j].iter().max().copied().unwrap_or(i32::min_value())
                    );
                }
            }
            assert_eq!(
                segtree.all_prod(),
                base.iter().max().copied().unwrap_or(i32::min_value())
            );
            for k in 0..=10 {
                let f = |&x: &i32| x < k;
                for i in 0..=n {
                    assert_eq!(
                        Some(segtree.max_right(i, f)),
                        (i..=n)
                            .filter(|&j| f(&base[i..j]
                                .iter()
                                .max()
                                .copied()
                                .unwrap_or(i32::min_value())))
                            .max()
                    );
                }
                for j in 0..=n {
                    assert_eq!(
                        Some(segtree.min_left(j, f)),
                        (0..=j)
                            .filter(|&i| f(&base[i..j]
                                .iter()
                                .max()
                                .copied()
                                .unwrap_or(i32::min_value())))
                            .min()
                    );
                }
            }
        }
    }
}

Submission Info

Judge Result