結果
| 問題 | No.2872 Depth of the Parentheses |
| ユーザー |
👑  Mizar
|
| 提出日時 | 2024-09-06 23:04:23 |
| 言語 | Rust (1.77.0 + proconio) |
| 結果 |
AC
|
| 実行時間 | 1 ms / 2,000 ms |
| コード長 | 63,386 bytes |
| コンパイル時間 | 14,251 ms |
| コンパイル使用メモリ | 402,776 KB |
| 実行使用メモリ | 6,944 KB |
| 最終ジャッジ日時 | 2024-09-06 23:05:03 |
| 合計ジャッジ時間 | 15,367 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge1 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
6,816 KB |
| testcase_01 | AC | 1 ms
6,812 KB |
| testcase_02 | AC | 1 ms
6,812 KB |
| testcase_03 | AC | 1 ms
6,816 KB |
| testcase_04 | AC | 1 ms
6,944 KB |
| testcase_05 | AC | 1 ms
6,940 KB |
| testcase_06 | AC | 1 ms
6,944 KB |
| testcase_07 | AC | 1 ms
6,944 KB |
| testcase_08 | AC | 1 ms
6,940 KB |
| testcase_09 | AC | 1 ms
6,940 KB |
| testcase_10 | AC | 1 ms
6,944 KB |
| testcase_11 | AC | 1 ms
6,940 KB |
| testcase_12 | AC | 1 ms
6,940 KB |
| testcase_13 | AC | 1 ms
6,940 KB |
| testcase_14 | AC | 1 ms
6,940 KB |
| testcase_15 | AC | 1 ms
6,940 KB |
| testcase_16 | AC | 1 ms
6,940 KB |
| testcase_17 | AC | 1 ms
6,940 KB |
| testcase_18 | AC | 1 ms
6,940 KB |
| testcase_19 | AC | 1 ms
6,940 KB |
| testcase_20 | AC | 1 ms
6,940 KB |
| testcase_21 | AC | 1 ms
6,944 KB |
| testcase_22 | AC | 1 ms
6,944 KB |
| evil_01.txt | WA | - |
| evil_02.txt | WA | - |
| evil_03.txt | WA | - |
| evil_04.txt | WA | - |
| evil_05.txt | WA | - |
ソースコード
// -*- coding:utf-8-unix -*-
pub use __cargo_equip::prelude::*;
use crate::__cargo_equip::crates::{input::*, obuf::*, rustc_hash::FxHashMap};
pub fn solve<I: NextToken>(input: &mut I) {
// Initialize.
#[rustfmt::skip] #[cfg(tcheck)] let tins = std::time::Instant::now();
#[rustfmt::skip] #[cfg(tcheck)] let mut durs = Vec::with_capacity(16);
use_input!(input);
let mut obuf = ProconWriteBuffer::with_capacity(1 << 26);
let mut out = std::io::stdout();
#[rustfmt::skip] #[cfg(tcheck)] durs.push((tins.elapsed(), "initial"));
input! {
x: u32, k: u32,
}
if k > 10 {
return;
}
use modint32static::ModIntStatic998244353 as MInt;
let plus = MInt::raw(x) / MInt::raw(100);
let minus = MInt::raw(100 - x) / MInt::raw(100);
let mut dp = FxHashMap::default();
dp.insert((0u32, 0u32), MInt::raw(1));
for i in (0u32..(2 * k)).rev() {
let mut ndp = FxHashMap::default();
for (&(cur, cmax), &par) in dp.iter() {
let ppar = plus * par;
let mpar = minus * par;
if ppar.val() > 0 && cur < i {
*ndp.entry((cur + 1, cmax.max(cur + 1)))
.or_insert(MInt::raw(0)) += ppar;
}
if mpar.val() > 0 && cur > 0 {
*ndp.entry((cur - 1, cmax)).or_insert(MInt::raw(0)) += mpar;
}
}
dp = ndp;
}
let mut result = MInt::raw(0);
for (&(cur, max), &par) in dp.iter() {
if cur == 0 {
result += MInt::raw(max) * par;
}
}
obuf.uint(result.val());
obuf.lf();
#[rustfmt::skip] #[cfg(tcheck)] durs.push((tins.elapsed(), "solve"));
obuf.write_all(&mut out);
#[rustfmt::skip] #[cfg(tcheck)] durs.push((tins.elapsed(), "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 = 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(|| launch_solver!(solve)).unwrap().join().unwrap();
} else {
launch_solver!(solve)
}
}
// The following code was expanded by `cargo-equip`.
/// # Bundled libraries
///
/// - `git+ssh://git@github.com/mizar/competitive-library-rs.git?rev=ae51655#mizar-competitive-integer-modint32static@0.0.0` licensed under `CC0-1.0` as `crate::__cargo_equip::crates::modint32static`
/// - `git+ssh://git@github.com/mizar/competitive-library-rs.git?rev=ae51655#mizar-competitive-io-input@0.0.0` licensed under `CC0-1.0` as `crate::__cargo_equip::crates::input`
/// - `git+ssh://git@github.com/mizar/competitive-library-rs.git?rev=ae51655#mizar-competitive-io-obuf@0.0.0` licensed under `CC0-1.0` as `crate::__cargo_equip::crates::obuf`
/// - `git+ssh://git@github.com/mizar/competitive-library-rs.git?rev=ae51655#mizar-competitive-misc-change@0.0.0` licensed under `CC0-1.0` as `crate::__cargo_equip::crates::change`
/// - `git+ssh://git@github.com/mizar/competitive-library-rs.git?rev=ae51655#mizar-competitive-misc-dec4le@0.0.0` licensed under `CC0-1.0` as `crate::__cargo_equip::crates::dec4le`
/// - `git+ssh://git@github.com/mizar/competitive-library-rs.git?rev=ae51655#mizar-competitive-misc-invariant@0.0.0` licensed under `CC0-1.0` as `crate::__cargo_equip::crates::invariant`
/// - `git+ssh://git@github.com/mizar/competitive-library-rs.git?rev=ae51655#mizar-competitive-misc-parseint@0.0.0` licensed under `CC0-1.0` as `crate::__cargo_equip::crates::parseint`
/// - `git+ssh://git@github.com/mizar/competitive-library-rs.git?rev=ae51655#mizar-competitive-misc-primint@0.0.0` licensed under `CC0-1.0` as `crate::__cargo_equip::crates::primint`
/// - `registry+https://github.com/rust-lang/crates.io-index#rustc-hash@1.1.0` licensed under `Apache-2.0/MIT` as `crate::__cargo_equip::crates::rustc_hash`
///
/// # License and Copyright Notices
///
/// - `registry+https://github.com/rust-lang/crates.io-index#rustc-hash@1.1.0`
///
/// ```text
/// Permission is hereby granted, free of charge, to any
/// person obtaining a copy of this software and associated
/// documentation files (the "Software"), to deal in the
/// Software without restriction, including without
/// limitation the rights to use, copy, modify, merge,
/// publish, distribute, sublicense, and/or sell copies of
/// the Software, and to permit persons to whom the Software
/// is furnished to do so, subject to the following
/// conditions:
///
/// The above copyright notice and this permission notice
/// shall be included in all copies or substantial portions
/// of the Software.
///
/// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF
/// ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
/// TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
/// PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT
/// SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
/// CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
/// OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR
/// IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
/// DEALINGS IN THE SOFTWARE.
/// ```
#[cfg_attr(any(), rustfmt::skip)]
#[allow(unused)]
mod __cargo_equip {
pub(crate) mod crates {
pub mod modint32static {use crate::__cargo_equip::preludes::modint32static::*;pub use crate::__cargo_equip::macros::modint32static::*;pub trait ModInt32Static{const MOD:u32;const TZ:u32;const MX:u32;const IMX:u32;const MYM:u32;const IBIN:[u32;64];fn norm_impl(n:u32)->u32;fn add_impl(lhs:u32,rhs:u32)->u32;fn sub_impl(lhs:u32,rhs:u32)->u32;fn mul_impl(lhs:u32,rhs:u32)->u32;fn mul_mx(lhs:u32,rhs:u32)->u32;fn pow_impl(lhs:u32,rhs:u32)->u32;fn div_impl(lhs:u32,rhs:u32)->Option<u32>;fn inv_plain(n:u32)->Option<u32>;fn inv_mx(n:u32)->Option<u32>;fn inv_my(n:u32)->Option<u32>;fn inv_impl(n:u32)->Option<u32>;}#[macro_export]macro_rules!__cargo_equip_macro_def_modint32static_modint32static_impl{($modulus:literal,$st:ident)=>{modint32static_impl!(@dol($)$modulus,$st);};(@dol($dol:tt)$modulus:literal,$st:ident)=>{#[derive(Copy,Clone)]pub struct$st(u32);impl ModInt32Static for$st{const MOD:u32=($modulus as u32);const TZ:u32=($modulus as u32).trailing_zeros();const MX:u32=(Self::MOD>>(Self::TZ&31))|((Self::MOD==0)as u32);const IMX:u32={let mx=Self::MX;let mut x=mx;x=x.wrapping_mul(2u32.wrapping_sub(mx.wrapping_mul(x)));x=x.wrapping_mul(2u32.wrapping_sub(mx.wrapping_mul(x)));x=x.wrapping_mul(2u32.wrapping_sub(mx.wrapping_mul(x)));x=x.wrapping_mul(2u32.wrapping_sub(mx.wrapping_mul(x)));x};const MYM:u32=((Self::TZ!=0)as u32).wrapping_neg()>>((32-Self::TZ)&31);const IBIN:[u32;64]={let mut ibin=[0u32;64];ibin[0]=1;const fn div2(x:u32,m:u32)->u32{x/2+((x&1).wrapping_neg()&(m/2+1))}macro_rules!div2{($dol($dol i:literal),*)=>{$dol(ibin[$dol i+1]=div2(ibin[$dol i],Self::MX);)*};}div2!(0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62);ibin};#[inline]fn norm_impl(x:u32)->u32{if Self::MOD==0{x}else{x%Self::MOD}}#[inline]fn add_impl(lhs:u32,rhs:u32)->u32{if Self::MOD==0{return lhs.wrapping_add(rhs);}let v=u64::from(lhs)+u64::from(rhs);match v.checked_sub(u64::from(Self::MOD)){None=>v as u32,Some(w)=>w as u32,}}#[inline]fn sub_impl(lhs:u32,rhs:u32)->u32{if Self::MOD==0{return lhs.wrapping_sub(rhs);}let(v,f)=lhs.overflowing_sub(rhs);v.wrapping_add(u32::from(f).wrapping_neg()&Self::MOD)}#[inline]fn mul_impl(lhs:u32,rhs:u32)->u32{if Self::MOD==0{return lhs.wrapping_mul(rhs);}(u64::from(lhs)*u64::from(rhs)%u64::from(Self::MOD))as u32}#[inline]fn mul_mx(lhs:u32,rhs:u32)->u32{(u64::from(lhs)*u64::from(rhs)%u64::from(Self::MX))as u32}#[inline]fn pow_impl(lhs:u32,mut rhs:u32)->u32{if rhs==0{return u32::from(Self::MOD!=1);}let mut t=lhs;while rhs%2==0{t=Self::mul_impl(t,t);rhs/=2;}let mut r=t;rhs/=2;while rhs!=0{t=Self::mul_impl(t,t);if rhs%2!=0{r=Self::mul_impl(r,t);}rhs/=2;}r}#[inline]fn div_impl(lhs:u32,rhs:u32)->Option<u32>{Self::inv_impl(rhs).map(|irhs|Self::mul_impl(lhs,irhs))}#[inline]fn inv_plain(n:u32)->Option<u32>{let m=Self::MOD;let(mut a,mut b,mut x,mut y)=(1,0,n,m);loop{match x{0=>break None,1=>break Some(a),_=>{}}b+=a*(y/x);y%=x;match y{0=>break None,1=>break Some(m-b),_=>{}}a+=b*(x/y);x%=y;}}#[inline]fn inv_mx(n:u32)->Option<u32>{if Self::MX%2==0{unsafe{core::hint::unreachable_unchecked()}}if Self::MX==1{return Some(0);}let(mut a,mut b,mut x,mut y)=(1,0,n,Self::MX);if x==0{return None;}let mut s=n.trailing_zeros();x>>=s;loop{if x==1{return Some(Self::mul_mx(a,Self::IBIN[s as usize]));}if x==y{return None;}if x<=(y>>3){if x==0{unsafe{core::hint::unreachable_unchecked()}}let(q,r)=(y/x,y%x);b+=a*q;y=r;if y==0{return None;}let t=y.trailing_zeros();y>>=t;a<<=t;s+=t;}else{while y>x{y-=x;b+=a;let t=y.trailing_zeros();y>>=t;a<<=t;s+=t;}}if y==1{return Some(Self::mul_mx(Self::MX-b,Self::IBIN[s as usize]));}if(x>>3)>=y{if y==0{unsafe{core::hint::unreachable_unchecked()}}let(q,r)=(x/y,x%y);a+=b*q;x=r;if x==0{return None;}let t=x.trailing_zeros();x>>=t;b<<=t;s+=t;}else{while x>y{x-=y;a+=b;let t=x.trailing_zeros();x>>=t;b<<=t;s+=t;}}}}#[inline]fn inv_my(n:u32)->Option<u32>{if Self::TZ==0{return Some(0);}if n%2==0{return None;}Some(Self::MYM&match Self::TZ{21..=0xffff_ffff=>{let mut t=n.wrapping_mul(3)^2;let mut u=1u32.wrapping_sub(t.wrapping_mul(n));t=t.wrapping_mul(u.wrapping_add(1));u=u.wrapping_mul(u);t=t.wrapping_mul(u.wrapping_add(1));u=u.wrapping_mul(u);t=t.wrapping_mul(u.wrapping_add(1));t}11..=20=>{let mut t=n.wrapping_mul(3)^2;let mut u=1u32.wrapping_sub(t.wrapping_mul(n));t=t.wrapping_mul(u.wrapping_add(1));u=u.wrapping_mul(u);t=t.wrapping_mul(u.wrapping_add(1));t}6..=10=>{let t=n.wrapping_mul(3)^2;t.wrapping_mul(2u32.wrapping_sub(n.wrapping_mul(t)))}4..=5=>n.wrapping_mul(3)^2,0..=3=>n,})}#[inline]fn inv_impl(n:u32)->Option<u32>{if Self::TZ==0{return Self::inv_mx(n);}if Self::MX==1{return Self::inv_my(n);}if let Some(y)=Self::inv_my(n){if let Some(x)=Self::inv_mx(n){let(t,f)=x.overflowing_sub(Self::MX*(Self::IMX.wrapping_mul(x.wrapping_sub(y))&Self::MYM));return Some(t.wrapping_add((f as u32).wrapping_neg()&Self::MOD));}}return None;}}impl std::ops::Add for$st{type Output=Self;#[inline]fn add(self,rhs:Self)->Self::Output{$st($st::add_impl(self.0,rhs.0))}}impl std::ops::Sub for$st{type Output=Self;#[inline]fn sub(self,rhs:Self)->Self::Output{$st($st::sub_impl(self.0,rhs.0))}}impl std::ops::Mul for$st{type Output=Self;#[inline]fn mul(self,rhs:Self)->Self::Output{$st($st::mul_impl(self.0,rhs.0))}}impl std::ops::Div for$st{type Output=Self;#[inline]fn div(self,rhs:Self)->Self::Output{$st($st::div_impl(self.0,rhs.0).unwrap())}}impl std::ops::Neg for$st{type Output=Self;#[inline]fn neg(self)->Self::Output{$st($st::sub_impl(0,self.0))}}impl std::ops::AddAssign for$st{#[inline]fn add_assign(&mut self,rhs:Self){*self=Self(Self::add_impl(self.0,rhs.0));}}impl std::ops::SubAssign for$st{#[inline]fn sub_assign(&mut self,rhs:Self){*self=Self(Self::sub_impl(self.0,rhs.0));}}impl std::ops::MulAssign for$st{#[inline]fn mul_assign(&mut self,rhs:Self){*self=Self(Self::mul_impl(self.0,rhs.0));}}impl std::ops::DivAssign for$st{#[inline]fn div_assign(&mut self,rhs:Self){*self=Self(Self::div_impl(self.0,rhs.0).unwrap());}}impl$st{#[inline]pub fn new(n:u32)->Self{Self(Self::norm_impl(n))}#[inline]pub fn raw(n:u32)->Self{debug_assert!(n<Self::MOD||Self::MOD==0);Self(n)}#[inline]pub fn val(&self)->u32{self.0}#[inline]pub fn pow(&self,r:u32)->Self{Self(Self::pow_impl(self.0,r))}#[inline]pub fn inv(&self)->Option<Self>{Self::inv_impl(self.0).map(|ni|Self(ni))}}};}macro_rules!modint32static_impl{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_modint32static_modint32static_impl!{$($tt)*})}modint32static_impl!(998244353,ModIntStatic998244353);modint32static_impl!(1000000007,ModIntStatic1000000007);}
pub mod input {use crate::__cargo_equip::preludes::input::*;pub use crate::__cargo_equip::macros::input::*;use crate::__cargo_equip::crates::invariant::*;pub use crate::__cargo_equip::crates::parseint::*;#[macro_export]macro_rules!__cargo_equip_macro_def_input_use_input{($input:ident)=>{use_input!(@dol($)$input);};(@dol($dol:tt)$input:ident)=>{#[macro_export]macro_rules!input{($dol($dol r:tt)*)=>{input_inner!{$input,$dol($dol r)*}};}#[macro_export]macro_rules!read{($dol t:tt)=>{{read_value!($input,$dol t)}};}};}macro_rules!use_input{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_input_use_input!{$($tt)*})}#[macro_export]macro_rules!__cargo_equip_macro_def_input_input_inner{($source:expr)=>{};($source:expr,)=>{};($source:expr,mut$var:ident:$t:tt$($r:tt)*)=>{let mut$var=read_value!($source,$t);input_inner!{$source$($r)*}};($source:expr,$var:ident:$t:tt$($r:tt)*)=>{let$var=read_value!($source,$t);input_inner!{$source$($r)*}};}macro_rules!input_inner{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_input_input_inner!{$($tt)*})}#[macro_export]macro_rules!__cargo_equip_macro_def_input_read_value{($source:expr,($($t:tt),*))=>{($(read_value!($source,$t)),*)};($source:expr,[$t:tt;$len:expr])=>{(0..$len).map(|_|read_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,u8_1)=>{$source.next_wordtoken().as_slice().parse_u8_raw()-1};($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)=>{{unsafe{String::from_utf8_unchecked($source.next_wordtoken().as_slice())}.parse::<$t>().expect("Parse error")}};}macro_rules!read_value{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_input_read_value!{$($tt)*})}unsafe fn ptr_offset_u8(dist:*const u8,origin:*const u8)->usize{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())}}pub trait NextToken{fn get_ascii_byte(&mut self)->u8;fn next_wordtoken(&mut self)->Token;fn next_linetoken(&mut self)->Token;}pub struct BytesIter<'a>(pub&'a[u8]);impl NextToken for BytesIter<'_>{fn get_ascii_byte(&mut self)->u8{while let[first,remain@..]=self.0{self.0=remain;if*first>0x20{return*first;}}panic!()}fn next_wordtoken(&mut self)->Token{while let[first,remain@..]=self.0{if*first<0x21{self.0=remain;}else{break;}}let mut split2=self.0.splitn(2,|&c|c<0x21);let cur=split2.next().unwrap_or(b"");self.0=split2.next().unwrap_or(b"");Token::Slice(cur)}fn next_linetoken(&mut self)->Token{while let[first,remain@..]=self.0{if*first<0x21{self.0=remain;}else{break;}}let mut split2=self.0.splitn(2,|&c|c==b'\n');let mut cur:&[u8]=split2.next().unwrap_or(b"");while let[remain@..,last]=cur{if*last<0x21{cur=remain;}else{break;}}self.0=split2.next().unwrap_or(b"");Token::Slice(cur)}}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:&[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{invariant!(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}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;}}}impl<R:std::io::BufRead>NextToken for ProconIBufIter<R>{fn get_ascii_byte(&mut self)->u8{self.get_ascii_byte_opt().unwrap()}#[inline]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]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);}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);}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,));}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,));}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 ProconParse{fn get_ascii_byte_opt(&mut self)->Option<u8>;}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,}}}}impl<R:std::io::BufRead>Drop for ProconIBufIter<R>{fn drop(&mut self){self.inner.consume(unsafe{ptr_offset_u8(self.ptr,self.raw)});}}#[cfg(target_os="linux")]#[link(name="c")]extern "C"{pub fn mmap(addr:*mut u8,length:usize,prot:i32,flags:i32,fd:i32,off:isize,)->*mut u8;pub fn munmap(addr:*mut u8,length:usize)->i32;pub fn read(fd:i32,buf:*mut u8,len:usize)->usize;}#[cfg(not(target_os="linux"))]#[macro_export]macro_rules!__cargo_equip_macro_def_input_launch_solver{($s:ident)=>{{let stdin=std::io::stdin();$s(&mut ProconIBufIter::new(stdin.lock()));}};}macro_rules!launch_solver{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_input_launch_solver!{$($tt)*})}#[cfg(target_os="linux")]#[macro_export]macro_rules!__cargo_equip_macro_def_input_launch_solver{($s:ident)=>{unsafe{use std::os::unix::io::FromRawFd;match std::fs::File::from_raw_fd(0).metadata(){Ok(metadata)if metadata.is_file()=>{let filelen=metadata.len();let input=mmap(std::ptr::null_mut(),filelen as usize,1,2,0,0);$s(&mut BytesIter(std::slice::from_raw_parts(input,filelen as usize,)));}_=>{let stdin=std::io::stdin();$s(&mut ProconIBufIter::new(stdin.lock()));}}}};}macro_rules!launch_solver{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_input_launch_solver!{$($tt)*})}}
pub mod obuf {use crate::__cargo_equip::preludes::obuf::*;pub use crate::__cargo_equip::crates::{dec4le::*,primint::*};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;}pub fn len(&self)->usize{unsafe{self.0.offset_from(self.1.as_ptr())as usize}}pub fn remain(&self)->usize{self.1.capacity()-self.len()}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>,{match U::BITS{0..=64=>unsafe{DEC4LE.raw_u64(&mut self.0,Into::<u128>::into(d)as u64)},_=>unsafe{DEC4LE.raw_u128(&mut self.0,Into::<u128>::into(d))},}}pub fn uint_spraw<U>(&mut self,d:U)where U:UPrimInt+std::convert::Into<u128>,{match U::BITS{0..=64=>unsafe{DEC4LE.raw_u64(&mut self.0,Into::<u128>::into(d)as u64);self.sp();},_=>unsafe{DEC4LE.raw_u128(&mut self.0,Into::<u128>::into(d));self.sp();},}}pub fn uint_sp<U>(&mut self,s:&[U])where U:UPrimInt+std::convert::Into<u128>,{if s.is_empty(){return;}let mut p=self.0;for&d in s.iter(){match U::BITS{0..=64=>unsafe{DEC4LE.raw_u64(&mut p,Into::<u128>::into(d)as u64);proconwritebuf_sp(&mut p);},_=>unsafe{DEC4LE.raw_u128(&mut p,Into::<u128>::into(d));proconwritebuf_sp(&mut p);},}}self.0=unsafe{p.sub(1)};}pub fn uint_splf<U>(&mut self,s:&[U])where U:UPrimInt+std::convert::Into<u128>,{if s.is_empty(){proconwritebuf_lf(&mut self.0);return;}let mut p=self.0;for&d in s.iter(){match U::BITS{0..=64=>unsafe{DEC4LE.raw_u64(&mut p,Into::<u128>::into(d)as u64);proconwritebuf_sp(&mut p);},_=>unsafe{DEC4LE.raw_u128(&mut p,Into::<u128>::into(d));proconwritebuf_sp(&mut p);},}}unsafe{*p.sub(1)=b'\n'};self.0=p;}pub fn usize(&mut self,d:usize){unsafe{DEC4LE.raw_u64(&mut self.0,d as u64)};}pub fn usize_spraw(&mut self,d:usize){unsafe{DEC4LE.raw_u64(&mut self.0,d as u64);self.sp();}}pub fn usize_sp(&mut self,s:&[usize]){if s.is_empty(){return;}let mut p=self.0;for&d in s.iter(){unsafe{DEC4LE.raw_u64(&mut p,d as u64);proconwritebuf_sp(&mut p);}}self.0=unsafe{p.sub(1)};}pub fn usize_splf(&mut self,s:&[usize]){if s.is_empty(){proconwritebuf_lf(&mut self.0);return;}let mut p=self.0;for&d in s.iter(){unsafe{DEC4LE.raw_u64(&mut p,d as u64);proconwritebuf_sp(&mut p);}}unsafe{*p.sub(1)=b'\n'};self.0=p;}pub fn iint<I>(&mut self,d:I)where I:IPrimInt+std::convert::Into<i128>,{match I::BITS{0..=64=>unsafe{DEC4LE.raw_i64(&mut self.0,Into::<i128>::into(d)as i64)},_=>unsafe{DEC4LE.raw_i128(&mut self.0,Into::<i128>::into(d))},}}pub fn iint_spraw<I>(&mut self,d:I)where I:IPrimInt+std::convert::Into<i128>,{match I::BITS{0..=64=>unsafe{DEC4LE.raw_i64(&mut self.0,Into::<i128>::into(d)as i64);self.sp();},_=>unsafe{DEC4LE.raw_i128(&mut self.0,Into::<i128>::into(d));self.sp();},}}pub fn iint_sp<I>(&mut self,s:&[I])where I:IPrimInt+std::convert::Into<i128>,{if s.is_empty(){return;}let mut p=self.0;for&d in s.iter(){match I::BITS{0..=64=>unsafe{DEC4LE.raw_i64(&mut p,Into::<i128>::into(d)as i64);proconwritebuf_sp(&mut p);},_=>unsafe{DEC4LE.raw_i128(&mut p,Into::<i128>::into(d));proconwritebuf_sp(&mut p);},}}self.0=unsafe{p.sub(1)};}pub fn iint_splf<I>(&mut self,s:&[I])where I:IPrimInt+std::convert::Into<i128>+std::convert::TryInto<u8>,{if s.is_empty(){proconwritebuf_lf(&mut self.0);return;}let mut p=self.0;for&d in s.iter(){match I::BITS{0..=64=>unsafe{DEC4LE.raw_i64(&mut p,Into::<i128>::into(d)as i64);proconwritebuf_sp(&mut p);},_=>unsafe{DEC4LE.raw_i128(&mut p,Into::<i128>::into(d));proconwritebuf_sp(&mut p);},}}unsafe{*p.sub(1)=b'\n'};self.0=p;}pub fn bslf(&mut self){unsafe{if self.0!=self.1.as_mut_ptr()&&*(self.0).sub(1)==b' '{*(self.0).sub(1)=b'\n';}else{*(self.0)=b'\n';self.0=self.0.add(1);}}}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 yes(&mut self,b:bool){proconwritebuf_bytes(&mut self.0,if b{b"yes"}else{b"no"});}#[allow(non_snake_case)]pub fn Yes(&mut self,b:bool){proconwritebuf_bytes(&mut self.0,if b{b"Yes"}else{b"No"});}#[allow(non_snake_case)]pub fn YES(&mut self,b:bool){proconwritebuf_bytes(&mut self.0,if b{b"YES"}else{b"NO"});}pub fn yes_lf(&mut self,b:bool){proconwritebuf_bytes(&mut self.0,if b{b"yes\n"}else{b"no\n"});}#[allow(non_snake_case)]pub fn Yes_lf(&mut self,b:bool){proconwritebuf_bytes(&mut self.0,if b{b"Yes\n"}else{b"No\n"});}#[allow(non_snake_case)]pub fn YES_lf(&mut self,b:bool){proconwritebuf_bytes(&mut self.0,if b{b"YES\n"}else{b"NO\n"});}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();}#[cfg(not(target_os="linux"))]pub fn write_all_stdout(&mut self){self.decision();let _=std::io::Write::write_all(&mut std::io::stdout(),self.1.as_slice());self.1.clear();self.0=self.1.as_mut_ptr();}#[cfg(not(target_os="linux"))]pub fn write_all_stderr(&mut self){self.decision();let _=std::io::Write::write_all(&mut std::io::stderr(),self.1.as_slice());self.1.clear();self.0=self.1.as_mut_ptr();}#[cfg(target_os="linux")]pub fn write_all_stdout(&mut self){self.decision();let mut s=self.1.as_slice();while!s.is_empty(){let l=unsafe{write(1,s.as_ptr(),s.len())};assert!(l>=0);s=&s[(l as usize)..];}self.1.clear();self.0=self.1.as_mut_ptr();}#[cfg(target_os="linux")]pub fn write_all_stderr(&mut self){self.decision();let mut s=self.1.as_slice();while!s.is_empty(){let l=unsafe{write(2,s.as_ptr(),s.len())};assert!(l>=0);s=&s[(l as usize)..];}self.1.clear();self.0=self.1.as_mut_ptr();}}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)};}#[cfg(target_os="linux")]#[link(name="c")]extern "C"{pub fn write(fd:i32,s:*const u8,len:usize)->isize;}}
pub mod change {pub 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 dec4le {use crate::__cargo_equip::preludes::dec4le::*;use crate::__cargo_equip::crates::invariant::*;pub struct Dec4le([u32;10000]);pub const DEC4LE:Dec4le=Dec4le::new();impl Dec4le{pub const fn new()->Self{let(mut d4,mut i)=([0u32;10000],0);while i<1_0000{let(dh,dl)=(i/100,i%100);d4[i as usize]=0x30303030|(dh/10)|((dh%10)<<8)|((dl/10)<<16)|((dl%10)<<24);i+=1;}Self(d4)}#[inline(always)]unsafe fn raw_d1(&self,v:&mut*mut u8,x:u32){invariant!(x<10);**v=b'0'|x as u8;*v=v.add(1);}#[inline(always)]unsafe fn raw_d2(&self,v:&mut*mut u8,x:u32){invariant!(x<100);v.copy_from_nonoverlapping((self.0[x as usize]>>16).to_le_bytes().as_ptr(),2);*v=v.add(2);}#[inline(always)]unsafe fn raw_d3(&self,v:&mut*mut u8,x:u32){invariant!(x<1000);v.copy_from_nonoverlapping((self.0[x as usize]>>8).to_le_bytes().as_ptr(),3);*v=v.add(3);}#[inline(always)]unsafe fn raw_d4(&self,v:&mut*mut u8,x:u32){invariant!(x<1_0000);v.copy_from_nonoverlapping(self.0[x as usize].to_le_bytes().as_ptr(),4);*v=v.add(4);}#[inline(always)]unsafe fn raw_d5(&self,v:&mut*mut u8,x:u32){invariant!(x<10_0000);let(y0,y1)=(x/10,x%10);v.copy_from_nonoverlapping((((y1 as u64)<<32)|(self.0[y0 as usize]as u64)|0x0030_0000_0000).to_le_bytes().as_ptr(),5,);*v=v.add(5);}#[inline(always)]unsafe fn raw_d6(&self,v:&mut*mut u8,x:u32){invariant!(x<100_0000);let(y0,y1)=(x/100,x%100);v.copy_from_nonoverlapping((((self.0[y1 as usize]as u64)>>16<<32)|(self.0[y0 as usize]as u64)).to_le_bytes().as_ptr(),6,);*v=v.add(6);}#[inline(always)]unsafe fn raw_d7(&self,v:&mut*mut u8,x:u32){invariant!(x<1000_0000);let(y0,y1)=(x/1000,x%1000);v.copy_from_nonoverlapping((((self.0[y1 as usize]as u64)>>8<<32)|(self.0[y0 as usize]as u64)).to_le_bytes().as_ptr(),7,);*v=v.add(7);}#[inline(always)]unsafe fn raw_d8(&self,v:&mut*mut u8,x:u32){invariant!(x<1_0000_0000);let(y0,y1)=(x/1_0000,x%1_0000);v.copy_from_nonoverlapping((((self.0[y1 as usize]as u64)<<32)|(self.0[y0 as usize]as u64)).to_le_bytes().as_ptr(),8,);*v=v.add(8);}#[inline(always)]unsafe fn raw_d16(&self,v:&mut*mut u8,x:u64){invariant!(x<1_0000_0000_0000_0000);let(y0,y1)=((x/1_0000_0000)as u32,(x%1_0000_0000)as u32);let(z0,z1,z2,z3)=(y0/1_0000,y0%1_0000,y1/1_0000,y1%1_0000);invariant!(z0<1_0000&&z1<1_0000&&z2<1_0000&&z3<1_0000);v.copy_from_nonoverlapping((((self.0[z3 as usize]as u128)<<96)|((self.0[z2 as usize]as u128)<<64)|((self.0[z1 as usize]as u128)<<32)|(self.0[z0 as usize]as u128)).to_le_bytes().as_ptr(),16,);*v=v.add(16);}#[inline(always)]pub unsafe fn raw_d8less(&self,v:&mut*mut u8,x:u32){invariant!(x<1_0000_0000);if x<1_0000{if x<100{match x{0..=9=>self.raw_d1(v,x),10..=99=>self.raw_d2(v,x),_=>core::hint::unreachable_unchecked(),}}else{match x{100..=999=>self.raw_d3(v,x),1000..=9999=>self.raw_d4(v,x),_=>core::hint::unreachable_unchecked(),}}}else{if x<100_0000{match x{1_0000..=9_9999=>self.raw_d5(v,x),10_0000..=99_9999=>self.raw_d6(v,x),_=>core::hint::unreachable_unchecked(),}}else{match x{100_0000..=999_9999=>self.raw_d7(v,x),1000_0000..=9999_9999=>self.raw_d8(v,x),_=>core::hint::unreachable_unchecked(),}}}}#[inline(always)]pub unsafe fn raw_u64(&self,v:&mut*mut u8,x:u64){match x{0..=9999_9999=>self.raw_d8less(v,x as u32),1_0000_0000u64..=9999_9999_9999_9999=>{let(z0,z1)=((x/1_0000_0000)as u32,(x%1_0000_0000)as u32);self.raw_d8less(v,z0);self.raw_d8(v,z1);}1_0000_0000_0000_0000..=1844_6744_0737_0955_1615=>{let(y0,y1)=((x/1_0000_0000_0000_0000)as u32,x%1_0000_0000_0000_0000,);invariant!(y0<1845);self.raw_d8less(v,y0);self.raw_d16(v,y1);}}}#[inline(always)]pub unsafe fn raw_u128(&self,v:&mut*mut u8,x:u128){match x{0..=9999_9999=>self.raw_d8less(v,x as u32),1_0000_0000..=9999_9999_9999_9999=>{let(z0,z1)=((x/1_0000_0000)as u32,(x%1_0000_0000)as u32);self.raw_d8less(v,z0);self.raw_d8(v,z1);}1_0000_0000_0000_0000..=1844_6744_0737_0955_1615=>{let(y0,y1)=((x/1_0000_0000_0000_0000)as u32,(x%1_0000_0000_0000_0000)as u64,);invariant!(y0<1845);self.raw_d8less(v,y0);self.raw_d16(v,y1);}1844_6744_0737_0955_1616..=9999_9999_9999_9999_9999_9999=>{let y0=(((x>>16)as u64 as u128)*4153837486827862103>>99)as u32;let y1=(x-(y0 as u128)*1_0000_0000_0000_0000)as u64;invariant!(y0<1_0000_0000);invariant!(y1<1_0000_0000_0000_0000);self.raw_d8less(v,y0);self.raw_d16(v,y1);}1_0000_0000_0000_0000_0000_0000..=9999_9999_9999_9999_9999_9999_9999_9999=>{let mut y0=((((x>>43)as u64 as u128)*16225927682921336)>>64)as u64;let mut y1=(x-(y0 as u128)*1_0000_0000_0000_0000)as u64;if let Some(yt)=y1.checked_sub(1_0000_0000_0000_0000){y1=yt;y0+=1;}invariant!(y0<1_0000_0000_0000_0000);invariant!(y1<1_0000_0000_0000_0000);let(z0,z1)=((y0/1_0000_0000)as u32,(y0%1_0000_0000)as u32);self.raw_d8less(v,z0);self.raw_d8(v,z1);self.raw_d16(v,y1);}1_0000_0000_0000_0000_0000_0000_0000_0000..=340_2823_6692_0938_4634_6337_4607_4317_6821_1455=>{let mut y0=((((x>>64)as u64 as u128)*3402823)>>64)as u32;let mut y1=x-(y0 as u128)*1_0000_0000_0000_0000_0000_0000_0000_0000;if let Some(yt)=y1.checked_sub(1_0000_0000_0000_0000_0000_0000_0000_0000){y1=yt;y0+=1;}invariant!(y0<340_2824);invariant!(y1<1_0000_0000_0000_0000_0000_0000_0000_0000);let mut z0=((((y1>>43)as u64 as u128)*16225927682921336)>>64)as u64;let mut z1=(y1-(z0 as u128)*1_0000_0000_0000_0000)as u64;if let Some(zt)=z1.checked_sub(1_0000_0000_0000_0000){z1=zt;z0+=1;}invariant!(z0<1_0000_0000_0000_0000);invariant!(z1<1_0000_0000_0000_0000);self.raw_d8less(v,y0);self.raw_d16(v,z0);self.raw_d16(v,z1);}}}#[inline(always)]pub unsafe fn raw_i64(&self,v:&mut*mut u8,x:i64){let x=if x<0{**v=b'-';*v=v.add(1);x.wrapping_neg()as u64}else{x as u64};self.raw_u64(v,x);}#[inline(always)]pub unsafe fn raw_i128(&self,v:&mut*mut u8,x:i128){let x=if x<0{**v=b'-';*v=v.add(1);x.wrapping_neg()as u128}else{x as u128};self.raw_u128(v,x);}}}
pub mod invariant {pub use crate::__cargo_equip::macros::invariant::*;#[macro_export]macro_rules!__cargo_equip_macro_def_invariant_invariant{($expr:expr)=>{debug_assert!($expr);if!($expr){#[allow(unused_unsafe)]unsafe{core::hint::unreachable_unchecked()};}};}macro_rules!invariant{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_invariant_invariant!{$($tt)*})}}
pub mod parseint {use crate::__cargo_equip::preludes::parseint::*;use crate::__cargo_equip::crates::invariant::invariant;use std::convert::TryInto;#[inline]pub fn parseuint_arith8le(a:u64)->u64{(((((a&0x0f0f0f0f0f0f0f0f).wrapping_mul((10<<8)+1)>>8)&0x00ff00ff00ff00ff).wrapping_mul((100<<16)+1)>>16)&0x0000ffff0000ffff).wrapping_mul((1_0000<<32)+1)>>32}#[inline]pub fn parseuint_arith8be(a:u64)->u64{(((((a&0x0f0f0f0f0f0f0f0f).wrapping_mul((1<<8)+10)>>8)&0x00ff00ff00ff00ff).wrapping_mul((1<<16)+100)>>16)&0x0000ffff0000ffff).wrapping_mul((1<<32)+1_0000)>>32}#[inline]pub fn parseuint_arith4le(a:u32)->u32{(((a&0x0f0f0f0f).wrapping_mul((10<<8)+1)>>8)&0x00ff00ff).wrapping_mul((100<<16)+1)>>16}#[inline]pub fn parseuint_arith4be(a:u32)->u32{(((a&0x0f0f0f0f).wrapping_mul((1<<8)+10)>>8)&0x00ff00ff).wrapping_mul((1<<16)+100)>>16}#[inline]pub fn parseuint_arith2le(a:u16)->u16{(a&0x0f0f).wrapping_mul((10<<8)+1)>>8}#[inline]pub fn parseuint_arith2be(a:u16)->u16{(a&0x0f0f).wrapping_mul((1<<8)+10)>>8}#[inline(always)]pub fn parseuint_arith1(a:u8)->u8{a&0x0f}#[inline(always)]pub fn parseuint_raw32b(s:[u8;32])->u128{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*1_0000_0000+b)as u128)*1_0000_0000_0000_0000+((c*1_0000_0000+d)as u128)}#[inline(always)]pub fn parseuint_raw16b(s:[u8;16])->u64{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*1_0000_0000+b}#[inline(always)]pub fn parseuint_raw8b(s:[u8;8])->u64{parseuint_arith8le(u64::from_le_bytes(s))}#[inline(always)]pub fn parseuint_raw7b(s:&[u8])->u64{invariant!(s.len()<=8);match s.len(){0=>0,1=>parseuint_arith1(s[0])as u64,2=>parseuint_arith2le(u16::from_le_bytes(s[0..2].try_into().unwrap()))as u64,3=>parseuint_arith4le(((s[0]as u32)<<8)|((u16::from_le_bytes(s[1..3].try_into().unwrap())as u32)<<16),)as u64,4=>parseuint_arith4le(u32::from_le_bytes(s[0..4].try_into().unwrap()))as u64,5=>parseuint_arith8le(((s[0]as u64)<<24)|((u32::from_le_bytes(s[1..5].try_into().unwrap())as u64)<<32),),6=>parseuint_arith8le(((u16::from_le_bytes(s[0..2].try_into().unwrap())as u64)<<16)|((u32::from_le_bytes(s[2..6].try_into().unwrap())as u64)<<32),),7=>parseuint_arith8le(((u32::from_le_bytes(s[0..4].try_into().unwrap())as u64)<<8)|((u32::from_le_bytes(s[3..7].try_into().unwrap())as u64)<<32),),_=>parseuint_arith8le(u64::from_le_bytes(s[0..8].try_into().unwrap())),}}#[inline(always)]pub fn parseuint_raw4b(s:[u8;4])->u32{parseuint_arith4le(u32::from_le_bytes(s))}#[inline(always)]pub fn parseuint_raw3b(s:&[u8])->u32{invariant!(s.len()<=4);match s.len(){0=>0,1=>parseuint_arith1(s[0])as u32,2=>parseuint_arith2le(u16::from_le_bytes(s[0..2].try_into().unwrap()))as u32,3=>parseuint_arith4le(((s[0]as u32)<<8)|((u16::from_le_bytes(s[1..3].try_into().unwrap())as u32)<<16),),_=>parseuint_arith4le(u32::from_le_bytes(s[0..4].try_into().unwrap())),}}#[inline(always)]pub fn parseuint_raw2b(s:[u8;2])->u16{parseuint_arith2le(u16::from_le_bytes(s))}#[inline(always)]pub fn parseuint_raw1b(s:u8)->u8{parseuint_arith1(s)}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;}impl ByteParseIntRaw for&[u8]{#[inline(always)]fn parse_u128_raw(&self)->u128{invariant!(self.len()<=39);invariant!(self.iter().all(u8::is_ascii_digit));match self.len(){0=>0,1=>parseuint_raw1b(self[0])as u128,2=>parseuint_raw2b(self[0..2].try_into().unwrap())as u128,3=>parseuint_arith4le(((self[0]as u32)<<8)|((u16::from_le_bytes(self[1..3].try_into().unwrap())as u32)<<16),)as u128,4=>parseuint_raw4b(self[0..4].try_into().unwrap())as u128,5=>parseuint_arith8le(((self[0]as u64)<<24)|((u32::from_le_bytes(self[1..5].try_into().unwrap())as u64)<<32),)as u128,6=>parseuint_arith8le(((u16::from_le_bytes(self[0..2].try_into().unwrap())as u64)<<16)|((u32::from_le_bytes(self[2..6].try_into().unwrap())as u64)<<32),)as u128,7=>parseuint_arith8le(((u32::from_le_bytes(self[0..4].try_into().unwrap())as u64)<<8)|((u32::from_le_bytes(self[3..7].try_into().unwrap())as u64)<<32),)as u128,8=>parseuint_raw8b(self[0..8].try_into().unwrap())as u128,9=>{((parseuint_raw1b(self[0])as u64)*1_0000_0000+parseuint_raw8b(self[1..9].try_into().unwrap()))as u128}10=>{((parseuint_raw2b(self[0..2].try_into().unwrap())as u64)*1_0000_0000+parseuint_raw8b(self[2..10].try_into().unwrap()))as u128}11=>{((parseuint_arith4le(u32::from_le_bytes(self[0..4].try_into().unwrap())<<8)as u64)*1_0000_0000+parseuint_raw8b(self[3..11].try_into().unwrap()))as u128}12=>{((parseuint_raw4b(self[0..4].try_into().unwrap())as u64)*1_0000_0000+parseuint_raw8b(self[4..12].try_into().unwrap()))as u128}13=>{(parseuint_arith8le(u64::from_le_bytes(self[0..8].try_into().unwrap())<<24)*1_0000_0000+parseuint_raw8b(self[5..13].try_into().unwrap()))as u128}14=>{(parseuint_arith8le(u64::from_le_bytes(self[0..8].try_into().unwrap())<<16)*1_0000_0000+parseuint_raw8b(self[6..14].try_into().unwrap()))as u128}15=>{(parseuint_arith8le(u64::from_le_bytes(self[0..8].try_into().unwrap())<<8)*1_0000_0000+parseuint_raw8b(self[7..15].try_into().unwrap()))as u128}16=>parseuint_raw16b(self[0..16].try_into().unwrap())as u128,17=>{((parseuint_raw1b(self[0])as u64)*1_0000_0000_0000_0000+parseuint_raw16b(self[1..17].try_into().unwrap()))as u128}18=>{((parseuint_raw2b(self[0..2].try_into().unwrap())as u64)*1_0000_0000_0000_0000+(parseuint_raw16b(self[2..18].try_into().unwrap())))as u128}19=>{((parseuint_arith4le(u32::from_le_bytes(self[0..4].try_into().unwrap())<<8)as u64)*1_0000_0000_0000_0000+(parseuint_raw16b(self[3..19].try_into().unwrap())))as u128}20=>{(parseuint_raw4b(self[0..4].try_into().unwrap())as u128)*1_0000_0000_0000_0000+(parseuint_raw16b(self[4..20].try_into().unwrap())as u128)}21=>{(parseuint_arith8le(u64::from_le_bytes(self[0..8].try_into().unwrap())<<24)as u128)*1_0000_0000_0000_0000+(parseuint_raw16b(self[5..21].try_into().unwrap())as u128)}22=>{(parseuint_arith8le(u64::from_le_bytes(self[0..8].try_into().unwrap())<<16)as u128)*1_0000_0000_0000_0000+(parseuint_raw16b(self[6..22].try_into().unwrap())as u128)}23=>{(parseuint_arith8le(u64::from_le_bytes(self[0..8].try_into().unwrap())<<8)as u128)*1_0000_0000_0000_0000+(parseuint_raw16b(self[7..23].try_into().unwrap())as u128)}24=>{(parseuint_raw8b(self[0..8].try_into().unwrap())as u128)*1_0000_0000_0000_0000+(parseuint_raw16b(self[8..24].try_into().unwrap())as u128)}25=>{(((parseuint_raw1b(self[0])as u64)*1_0000_0000+parseuint_raw8b(self[1..9].try_into().unwrap()))as u128)*1_0000_0000_0000_0000+(parseuint_raw16b(self[9..25].try_into().unwrap())as u128)}26=>{(((parseuint_raw2b(self[0..2].try_into().unwrap())as u64)*1_0000_0000+parseuint_raw8b(self[2..10].try_into().unwrap()))as u128)*1_0000_0000_0000_0000+(parseuint_raw16b(self[10..26].try_into().unwrap())as u128)}27=>{(((parseuint_arith4le(u32::from_le_bytes(self[0..4].try_into().unwrap())<<8)as u64)*1_0000_0000+parseuint_raw8b(self[3..11].try_into().unwrap()))as u128)*1_0000_0000_0000_0000+(parseuint_raw16b(self[11..27].try_into().unwrap())as u128)}28=>{(((parseuint_raw4b(self[0..4].try_into().unwrap())as u64)*1_0000_0000+parseuint_raw8b(self[4..12].try_into().unwrap()))as u128)*1_0000_0000_0000_0000+(parseuint_raw16b(self[12..28].try_into().unwrap())as u128)}29=>{(((parseuint_arith8le(u64::from_le_bytes(self[0..8].try_into().unwrap())<<24)as u64)*1_0000_0000+parseuint_raw8b(self[5..13].try_into().unwrap()))as u128)*1_0000_0000_0000_0000+(parseuint_raw16b(self[13..29].try_into().unwrap())as u128)}30=>{(((parseuint_arith8le(u64::from_le_bytes(self[0..8].try_into().unwrap())<<16)as u64)*1_0000_0000+parseuint_raw8b(self[6..14].try_into().unwrap()))as u128)*1_0000_0000_0000_0000+(parseuint_raw16b(self[14..30].try_into().unwrap())as u128)}31=>{(((parseuint_arith8le(u64::from_le_bytes(self[0..8].try_into().unwrap())<<8)as u64)*1_0000_0000+parseuint_raw8b(self[7..15].try_into().unwrap()))as u128)*1_0000_0000_0000_0000+(parseuint_raw16b(self[15..31].try_into().unwrap())as u128)}32=>parseuint_raw32b(self[0..32].try_into().unwrap()),33=>{parseuint_raw32b(self[0..32].try_into().unwrap())*10+(parseuint_raw1b(self[32])as u128)}34=>{parseuint_raw32b(self[0..32].try_into().unwrap())*100+(parseuint_raw2b(self[32..34].try_into().unwrap())as u128)}35=>{parseuint_raw32b(self[0..32].try_into().unwrap())*1000+(parseuint_arith4le(u32::from_le_bytes(self[31..35].try_into().unwrap())&0x0f0f0f00,)as u128)}36=>{parseuint_raw32b(self[0..32].try_into().unwrap())*1_0000+(parseuint_raw4b(self[32..36].try_into().unwrap())as u128)}37=>{parseuint_raw32b(self[0..32].try_into().unwrap())*10_0000+(parseuint_arith8le(u64::from_le_bytes(self[29..37].try_into().unwrap())&0x0f0f_0f0f_0f00_0000,)as u128)}38=>{parseuint_raw32b(self[0..32].try_into().unwrap())*100_0000+(parseuint_arith8le(u64::from_le_bytes(self[30..38].try_into().unwrap())&0x0f0f_0f0f_0f0f_0000,)as u128)}_=>{parseuint_raw32b(self[0..32].try_into().unwrap())*1000_0000+(parseuint_arith8le(u64::from_le_bytes(self[31..39].try_into().unwrap())&0x0f0f_0f0f_0f0f_0f00,)as u128)}}}#[inline(always)]fn parse_u64_raw(&self)->u64{invariant!(self.len()<=20);invariant!(self.iter().all(u8::is_ascii_digit));match self.len(){0=>0,1=>parseuint_raw1b(self[0])as u64,2=>parseuint_raw2b(self[0..2].try_into().unwrap())as u64,3=>parseuint_arith4le(((self[0]as u32)<<8)|((u16::from_le_bytes(self[1..3].try_into().unwrap())as u32)<<16),)as u64,4=>parseuint_raw4b(self[0..4].try_into().unwrap())as u64,5=>parseuint_arith8le(((self[0]as u64)<<24)|((u32::from_le_bytes(self[1..5].try_into().unwrap())as u64)<<32),),6=>parseuint_arith8le(((u16::from_le_bytes(self[0..2].try_into().unwrap())as u64)<<16)|((u32::from_le_bytes(self[2..6].try_into().unwrap())as u64)<<32),),7=>parseuint_arith8le(((u32::from_le_bytes(self[0..4].try_into().unwrap())as u64)<<8)|((u32::from_le_bytes(self[3..7].try_into().unwrap())as u64)<<32),),8=>parseuint_raw8b(self[0..8].try_into().unwrap()),9=>{(parseuint_arith1(self[0])as u64)*1_0000_0000+parseuint_raw8b(self[1..9].try_into().unwrap())}10=>{(parseuint_arith2le(u16::from_le_bytes(self[0..2].try_into().unwrap()))as u64)*1_0000_0000+parseuint_raw8b(self[2..10].try_into().unwrap())}11=>{(parseuint_arith4le(u32::from_le_bytes(self[0..4].try_into().unwrap())<<8)as u64)*1_0000_0000+parseuint_raw8b(self[3..11].try_into().unwrap())}12=>{(parseuint_arith4le(u32::from_le_bytes(self[0..4].try_into().unwrap()))as u64)*1_0000_0000+parseuint_raw8b(self[4..12].try_into().unwrap())}13=>{parseuint_arith8le(u64::from_le_bytes(self[0..8].try_into().unwrap())<<24)*1_0000_0000+parseuint_raw8b(self[5..13].try_into().unwrap())}14=>{parseuint_arith8le(u64::from_le_bytes(self[0..8].try_into().unwrap())<<16)*1_0000_0000+parseuint_raw8b(self[6..14].try_into().unwrap())}15=>{parseuint_arith8le(u64::from_le_bytes(self[0..8].try_into().unwrap())<<8)*1_0000_0000+parseuint_raw8b(self[7..15].try_into().unwrap())}16=>parseuint_raw16b(self[0..16].try_into().unwrap()),17=>{(parseuint_arith1(self[0])as u64)*1_0000_0000_0000_0000+parseuint_raw16b(self[1..17].try_into().unwrap())}18=>{(parseuint_arith2le(u16::from_le_bytes(self[0..2].try_into().unwrap()))as u64)*1_0000_0000_0000_0000+parseuint_raw16b(self[2..18].try_into().unwrap())}19=>{(parseuint_arith4le(u32::from_le_bytes(self[0..4].try_into().unwrap())<<8)as u64)*1_0000_0000_0000_0000+parseuint_raw16b(self[3..19].try_into().unwrap())}_=>{(parseuint_arith4le(u32::from_le_bytes(self[0..4].try_into().unwrap()))as u64)*1_0000_0000_0000_0000+(parseuint_raw16b(self[4..20].try_into().unwrap()))}}}#[inline(always)]fn parse_u32_raw(&self)->u32{invariant!(self.len()<=10);invariant!(self.iter().all(u8::is_ascii_digit));match self.len(){0=>0,1=>parseuint_raw1b(self[0])as u32,2=>parseuint_raw2b(self[0..2].try_into().unwrap())as u32,3=>parseuint_arith4le(((self[0]as u32)<<8)|((u16::from_le_bytes(self[1..3].try_into().unwrap())as u32)<<16),),4=>parseuint_raw4b(self[0..4].try_into().unwrap()),5=>parseuint_arith8le(((self[0]as u64)<<24)|((u32::from_le_bytes(self[1..5].try_into().unwrap())as u64)<<32),)as u32,6=>parseuint_arith8le(((u16::from_le_bytes(self[0..2].try_into().unwrap())as u64)<<16)|((u32::from_le_bytes(self[2..6].try_into().unwrap())as u64)<<32),)as u32,7=>parseuint_arith8le(((u32::from_le_bytes(self[0..4].try_into().unwrap())as u64)<<8)|((u32::from_le_bytes(self[3..7].try_into().unwrap())as u64)<<32),)as u32,8=>parseuint_raw8b(self[0..8].try_into().unwrap())as u32,9=>{(parseuint_arith1(self[0])as u32)*1_0000_0000+parseuint_raw8b(self[1..9].try_into().unwrap())as u32}_=>{(parseuint_arith2le(u16::from_le_bytes(self[0..2].try_into().unwrap()))as u32)*1_0000_0000+(parseuint_raw8b(self[2..10].try_into().unwrap())as u32)}}}#[inline(always)]fn parse_u16_raw(&self)->u16{invariant!(self.len()<=5);invariant!(self.iter().all(u8::is_ascii_digit));parseuint_raw7b(self)as u16}#[inline(always)]fn parse_u8_raw(&self)->u8{invariant!(self.len()<=3);invariant!(self.iter().all(u8::is_ascii_digit));parseuint_raw3b(self)as u8}#[inline(always)]fn parse_i128_raw(&self)->i128{invariant!(!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}}#[inline(always)]fn parse_i64_raw(&self)->i64{invariant!(!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}}#[inline(always)]fn parse_i32_raw(&self)->i32{invariant!(!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}}#[inline(always)]fn parse_i16_raw(&self)->i16{invariant!(!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}}#[inline(always)]fn parse_i8_raw(&self)->i8{invariant!(!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}}}}
pub mod primint {use std::ops;pub trait UPrimInt:Copy+Default+std::cmp::Ord+ops::Add<Output=Self>+ops::Sub<Output=Self>+ops::Mul<Output=Self>+ops::Div<Output=Self>+ops::Rem<Output=Self>+ops::AddAssign+ops::SubAssign+ops::MulAssign+ops::DivAssign+ops::RemAssign+ops::Shl<u32,Output=Self>+ops::Shr<u32,Output=Self>+ops::ShlAssign<u32>+ops::ShrAssign<u32>+ops::BitAnd<Output=Self>+ops::BitOr<Output=Self>+ops::BitXor<Output=Self>+ops::BitAndAssign+ops::BitOrAssign+ops::BitXorAssign+std::convert::From<u8>{const BITS:u32;fn count_zeros(self)->u32;fn count_ones(self)->u32;fn trailing_zeros(self)->u32;fn leading_zeros(self)->u32;fn checked_add(self,rhs:Self)->Option<Self>;fn checked_sub(self,rhs:Self)->Option<Self>;fn checked_mul(self,rhs:Self)->Option<Self>;fn checked_pow(self,exp:u32)->Option<Self>;fn wrapping_add(self,rhs:Self)->Self;fn wrapping_sub(self,rhs:Self)->Self;fn wrapping_neg(self)->Self;fn wrapping_mul(self,rhs:Self)->Self;fn overflowing_add(self,rhs:Self)->(Self,bool);fn overflowing_sub(self,rhs:Self)->(Self,bool);fn overflowing_neg(self)->(Self,bool);fn overflowing_mul(self,rhs:Self)->(Self,bool);fn pow(self,exp:u32)->Self;fn zero()->Self;fn one()->Self;fn is_zero(self)->bool;fn as_u8(self)->u8;fn as_u16(self)->u16;fn as_u32(self)->u32;fn as_u64(self)->u64;fn as_u128(self)->u128;fn as_usize(self)->usize;fn from_u32(x:u32)->Self;fn from_u64(x:u64)->Self;fn from_u128(x:u128)->Self;fn from_usize(x:usize)->Self;}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 count_ones(self)->u32{self.count_ones()}fn trailing_zeros(self)->u32{self.trailing_zeros()}fn leading_zeros(self)->u32{self.leading_zeros()}fn checked_add(self,rhs:$t)->Option<$t>{self.checked_add(rhs)}fn checked_sub(self,rhs:$t)->Option<$t>{self.checked_sub(rhs)}fn checked_mul(self,rhs:$t)->Option<$t>{self.checked_mul(rhs)}fn checked_pow(self,exp:u32)->Option<$t>{self.checked_pow(exp)}fn wrapping_add(self,rhs:$t)->$t{self.wrapping_add(rhs)}fn wrapping_sub(self,rhs:$t)->$t{self.wrapping_sub(rhs)}fn wrapping_neg(self)->$t{self.wrapping_neg()}fn wrapping_mul(self,rhs:$t)->$t{self.wrapping_mul(rhs)}fn overflowing_add(self,rhs:$t)->($t,bool){self.overflowing_add(rhs)}fn overflowing_sub(self,rhs:$t)->($t,bool){self.overflowing_sub(rhs)}fn overflowing_neg(self)->($t,bool){self.overflowing_neg()}fn overflowing_mul(self,rhs:$t)->($t,bool){self.overflowing_mul(rhs)}fn pow(self,exp:u32)->Self{self.pow(exp)}fn zero()->$t{0 as$t}fn one()->$t{1 as$t}fn is_zero(self)->bool{self==(0 as$t)}fn as_u8(self)->u8{self as u8}fn as_u16(self)->u16{self as u16}fn as_u32(self)->u32{self as u32}fn as_u64(self)->u64{self as u64}fn as_u128(self)->u128{self as u128}fn as_usize(self)->usize{self as usize}fn from_u32(x:u32)->Self{x as Self}fn from_u64(x:u64)->Self{x as Self}fn from_u128(x:u128)->Self{x as Self}fn from_usize(x:usize)->Self{x as Self}}};}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+ops::Add<Output=Self>+ops::Sub<Output=Self>+ops::Neg<Output=Self>+ops::Mul<Output=Self>+ops::Div<Output=Self>+ops::Rem<Output=Self>+std::convert::From<i8>{const BITS:u32;fn zero()->Self;fn one()->Self;fn is_zero(self)->bool;}macro_rules!impl_iprimint{($t:ty)=>{impl IPrimInt for$t{const BITS:u32=(0 as$t).count_zeros();fn zero()->$t{0 as$t}fn one()->$t{1 as$t}fn is_zero(self)->bool{self==(0 as$t)}}};}impl_iprimint!(i8);impl_iprimint!(i16);impl_iprimint!(i32);impl_iprimint!(i64);impl_iprimint!(i128);impl_iprimint!(isize);}
pub mod rustc_hash {#![no_std]extern crate std;use core::convert::TryInto;use core::default::Default;use core::hash::BuildHasherDefault;use core::hash::Hasher;use core::mem::size_of;use core::ops::BitXor;use std::collections::{HashMap,HashSet};pub type FxHashMap<K,V> =HashMap<K,V,BuildHasherDefault<FxHasher>>;pub type FxHashSet<V> =HashSet<V,BuildHasherDefault<FxHasher>>;pub struct FxHasher{hash:usize,}#[cfg(target_pointer_width="32")]const K:usize=0x9e3779b9;#[cfg(target_pointer_width="64")]const K:usize=0x517cc1b727220a95;impl Default for FxHasher{#[inline]fn default()->FxHasher{FxHasher{hash:0}}}impl FxHasher{#[inline]fn add_to_hash(&mut self,i:usize){self.hash=self.hash.rotate_left(5).bitxor(i).wrapping_mul(K);}}impl Hasher for FxHasher{#[inline]fn write(&mut self,mut bytes:&[u8]){#[cfg(target_pointer_width="32")]let read_usize=|bytes:&[u8]|u32::from_ne_bytes(bytes[..4].try_into().unwrap());#[cfg(target_pointer_width="64")]let read_usize=|bytes:&[u8]|u64::from_ne_bytes(bytes[..8].try_into().unwrap());let mut hash=FxHasher{hash:self.hash};assert!(size_of::<usize>()<=8);while bytes.len()>=size_of::<usize>(){hash.add_to_hash(read_usize(bytes)as usize);bytes=&bytes[size_of::<usize>()..];}if(size_of::<usize>()>4)&&(bytes.len()>=4){hash.add_to_hash(u32::from_ne_bytes(bytes[..4].try_into().unwrap())as usize);bytes=&bytes[4..];}if(size_of::<usize>()>2)&&bytes.len()>=2{hash.add_to_hash(u16::from_ne_bytes(bytes[..2].try_into().unwrap())as usize);bytes=&bytes[2..];}if(size_of::<usize>()>1)&&bytes.len()>=1{hash.add_to_hash(bytes[0]as usize);}self.hash=hash.hash;}#[inline]fn write_u8(&mut self,i:u8){self.add_to_hash(i as usize);}#[inline]fn write_u16(&mut self,i:u16){self.add_to_hash(i as usize);}#[inline]fn write_u32(&mut self,i:u32){self.add_to_hash(i as usize);}#[cfg(target_pointer_width="32")]#[inline]fn write_u64(&mut self,i:u64){self.add_to_hash(i as usize);self.add_to_hash((i>>32)as usize);}#[cfg(target_pointer_width="64")]#[inline]fn write_u64(&mut self,i:u64){self.add_to_hash(i as usize);}#[inline]fn write_usize(&mut self,i:usize){self.add_to_hash(i);}#[inline]fn finish(&self)->u64{self.hash as u64}}}
}
pub(crate) mod macros {
pub mod modint32static {pub use crate::__cargo_equip_macro_def_modint32static_modint32static_impl as modint32static_impl;}
pub mod input {pub use crate::{__cargo_equip_macro_def_input_input_inner as input_inner,__cargo_equip_macro_def_input_launch_solver as launch_solver,__cargo_equip_macro_def_input_read_value as read_value,__cargo_equip_macro_def_input_use_input as use_input};}
pub mod obuf {}
pub mod change {}
pub mod dec4le {}
pub mod invariant {pub use crate::__cargo_equip_macro_def_invariant_invariant as invariant;}
pub mod parseint {}
pub mod primint {}
pub mod rustc_hash {}
}
pub(crate) mod prelude {pub use crate::__cargo_equip::crates::*;}
mod preludes {
pub mod modint32static {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::invariant;}
pub mod input {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::{invariant,parseint,primint};}
pub mod obuf {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::{dec4le,invariant,primint};}
pub mod change {}
pub mod dec4le {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::invariant;}
pub mod invariant {}
pub mod parseint {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::{invariant,primint};}
pub mod primint {}
pub mod rustc_hash {}
}
}