// codesnip-guard: fastio
#[cfg_attr(any(),rustfmt::skip)]pub use self::fast_print::{FastIterPrint,FastPrint};#[cfg_attr(any(),rustfmt::skip)]pub use self::fastio::{BufferedInput,FastInput,FastOutput};#[cfg_attr(any(),rustfmt::skip)]mod fast_print{use super::FastOutput;use std::{fmt::Write as _,io::Write};pub trait FastPrint{fn fast_print<W:Write>(&self,writer:&mut FastOutput<W>);}impl FastPrint for(){#[inline]fn fast_print<W:Write>(&self,_writer:&mut FastOutput<W>){}}macro_rules!impl_fast_print_integer{($($ty:ident)*)=>{$(impl FastPrint for$ty{#[inline(always)]fn fast_print<W:Write>(&self,writer:&mut FastOutput<W>){writer.$ty(*self);}})*};}impl_fast_print_integer!(u8 u16 u32 u64 u128 usize i8 i16 i32 i64 i128 isize);impl FastPrint for str{#[inline]fn fast_print<W:Write>(&self,writer:&mut FastOutput<W>){writer.bytes(self.as_bytes());}}impl FastPrint for String{#[inline]fn fast_print<W:Write>(&self,writer:&mut FastOutput<W>){self.as_str().fast_print(writer);}}impl FastPrint for char{#[inline(always)]fn fast_print<W:Write>(&self,writer:&mut FastOutput<W>){if self.is_ascii(){writer.byte(*self as u8);}else{writer.bytes(self.encode_utf8(&mut[0;4]).as_bytes());}}}impl<T:FastPrint+?Sized>FastPrint for&T{#[inline]fn fast_print<W:Write>(&self,writer:&mut FastOutput<W>){T::fast_print(self,writer);}}macro_rules!impl_fast_print_display{($($ty:ty)*)=>{$(impl FastPrint for$ty{fn fast_print<W:Write>(&self,writer:&mut FastOutput<W>){write!(writer,"{}",self).expect("io error");}})*};}impl_fast_print_display!(bool f32 f64);pub trait FastIterPrint{fn fast_iter_print<W:Write,S:FastPrint>(self,writer:&mut FastOutput<W>,sep:S,is_head:bool);}macro_rules!impl_fast_iter_print_tuple{(@impl)=>{impl FastIterPrint for(){#[inline]fn fast_iter_print<W:Write,S:FastPrint>(self,_writer:&mut FastOutput<W>,_sep:S,_is_head:bool){}}};(@impl$T:ident$v:ident$($U:ident$u:ident)*)=>{impl<$T:FastPrint,$($U:FastPrint),*>FastIterPrint for($T,$($U,)*){#[inline]fn fast_iter_print<W:Write,S:FastPrint>(self,writer:&mut FastOutput<W>,sep:S,is_head:bool){let($v,$($u,)*)=self;if!is_head{sep.fast_print(writer);}$v.fast_print(writer);$(sep.fast_print(writer);$u.fast_print(writer);)*}}};(@inner[$($T:ident$v:ident)*]$U:ident$u:ident$($Rest:tt)*)=>{impl_fast_iter_print_tuple!(@impl$($T$v)*);impl_fast_iter_print_tuple!(@inner[$($T$v)*$U$u]$($Rest)*);};(@inner[$($T:ident$v:ident)*])=>{impl_fast_iter_print_tuple!(@impl$($T$v)*);};($($t:tt)*)=>{impl_fast_iter_print_tuple!(@inner[]$($t)*);};}impl_fast_iter_print_tuple!(A a B b C c D d E e F f G g H h I i J j K k);}#[cfg_attr(any(),rustfmt::skip)]mod fast_scanner{use super::{FastInput,ScanSource,advise_huge_pages};use std::str::from_utf8_unchecked;macro_rules!impl_fast_scan_integer{($($ty:ty,$read:ident,$method:ident);*$(;)?)=>{$(#[inline]fn$read(&mut self)->Option<$ty>{Some(unsafe{self.$method()})})*};}impl ScanSource for FastInput<'_>{fn read_u32_vec(&mut self,size:usize,capacity:usize)->Vec<u32>{let mut values=Vec::with_capacity(capacity.max(size));advise_huge_pages(&mut values);unsafe{self.extend_u32(&mut values,size)};values}#[inline]fn skip_whitespace(&mut self){self.skip_whitespace();}#[inline]fn next_token(&mut self)->Option<&str>{Some(unsafe{from_utf8_unchecked(self.bytes())})}impl_fast_scan_integer!(u8,read_u8,u8;u16,read_u16,u16;u32,read_u32,u32;u64,read_u64,u64;u128,read_u128,u128;usize,read_usize,usize;i8,read_i8,i8;i16,read_i16,i16;i32,read_i32,i32;i64,read_i64,i64;i128,read_i128,i128;isize,read_isize,isize;);}}#[cfg_attr(any(),rustfmt::skip)]mod fastio{use super::ScanSource;use std::{fmt,fs::File,io::{Read,Write,stdout},marker::PhantomData,os::fd::AsFd,ptr,str::FromStr};#[cfg(target_os="linux")]use std::ffi::{c_int,c_void};#[cfg(target_os="linux")]unsafe extern "C"{fn mmap(addr:*mut c_void,len:usize,prot:c_int,flags:c_int,fd:c_int,offset:isize)->*mut c_void;fn munmap(addr:*mut c_void,len:usize)->c_int;fn getpagesize()->c_int;}#[doc=" Token reader for little-endian targets. Integer reads require a decimal"]#[doc=" representation that fits the requested type, with at most that type's maximum"]#[doc=" number of digits and an optional `-` for signed types."]#[doc=""]#[doc=" Every read, including iterator reads, must start at an available token."]#[doc=" Reads consume exactly one trailing ASCII whitespace byte. `parse` and"]#[doc=" `ScanSource` require UTF-8. Slices returned by `bytes` must not outlive the input"]#[doc=" allocation. `bytes` and `parse` may also read an empty field at a delimiter."]pub struct FastInput<'input>{ptr:*const u8,end:*const u8,_marker:PhantomData<&'input[u8]>}impl<'input>FastInput<'input>{#[doc=" Reads all of stdin and retains its storage until process exit."]#[doc=""]#[doc=" # Safety"]#[doc=" Call before any other stdin reads. A mapped input file must not be modified"]#[doc=" while its contents or slices returned by this reader are in use."]#[doc=" Subsequent `ScanSource` reads must satisfy this type's token requirements."]pub unsafe fn stdin()->Self{let mut stdin=File::from(std::io::stdin().as_fd().try_clone_to_owned().unwrap());#[cfg(target_os="linux")]unsafe{if let Ok(metadata)=stdin.metadata()&&metadata.is_file()&&metadata.len()!=0{let len=metadata.len()as usize;let page=getpagesize()as usize;let mapped=len.div_ceil(page)*page;let reserved=mapped+page;let region=mmap(ptr::null_mut(),reserved,1,2|0x20,-1,0);if region as isize!=-1{if mmap(region,len,1,2|0x10,0,0)as isize!=-1{return FastInput{ptr:region.cast(),end:region.cast::<u8>().add(len),_marker:PhantomData};}assert_eq!(munmap(region,reserved),0);}}}let mut buf=Vec::new();stdin.read_to_end(&mut buf).unwrap();let len=buf.len();buf.resize(len+16,b' ');let ptr=Box::into_raw(buf.into_boxed_slice()).cast::<u8>();FastInput{ptr,end:unsafe{ptr.add(len)},_marker:PhantomData}}#[doc=" # Safety"]#[doc=" `s` must contain at least 16 initialized padding bytes after its final"]#[doc=" token delimiter. Its allocation must remain valid and unchanged while"]#[doc=" this reader or any slices returned by it are in use."]#[doc=" Subsequent `ScanSource` reads must satisfy this type's token requirements."]pub unsafe fn from_slice(s:&'input[u8])->Self{FastInput{ptr:s.as_ptr(),end:unsafe{s.as_ptr().add(s.len()-16)},_marker:PhantomData}}#[doc=" Skips ASCII whitespace without advancing beyond the input."]#[inline]pub fn skip_whitespace(&mut self){unsafe{while self.ptr<self.end&&(*self.ptr).is_ascii_whitespace(){self.ptr=self.ptr.add(1);}}}#[inline]unsafe fn fetch_ud4(&mut self)->u16{unsafe{let mut x:u32=ptr::read_unaligned(self.ptr as*const u32);x^=0x30303030;let tmp=(x&0xf0f0f0f0).trailing_zeros()>>3;x<<=32-(tmp<<3);x=x.wrapping_mul(10).wrapping_add(x>>8)&0x00ff00ff;x=x.wrapping_mul(100).wrapping_add(x>>16)&0x0000ffff;self.ptr=self.ptr.add((tmp+1)as usize);x as u16}}#[inline]unsafe fn fetch_ud8(&mut self)->u32{unsafe{let mut x:u64=ptr::read_unaligned(self.ptr as*const u64);x^=0x3030303030303030;let tmp=(x&0xf0f0f0f0f0f0f0f0).trailing_zeros()>>3;x<<=64-(tmp<<3);x=x.wrapping_mul(10).wrapping_add(x>>8)&0x00ff00ff00ff00ff;x=x.wrapping_mul(100).wrapping_add(x>>16)&0x0000ffff0000ffff;x=x.wrapping_mul(10000).wrapping_add(x>>32)&0x00000000ffffffff;self.ptr=self.ptr.add((tmp+1)as usize);x as u32}}#[inline]pub unsafe fn u8(&mut self)->u8{unsafe{self.fetch_ud4()as u8}}#[inline]pub unsafe fn u16(&mut self)->u16{unsafe{self.fetch_ud8()as u16}}#[doc=" 0..=99_999_999"]#[inline]pub unsafe fn u32_small(&mut self)->u32{unsafe{self.fetch_ud8()}}#[inline]pub unsafe fn u32(&mut self)->u32{unsafe{let mut x=u64::from_le(ptr::read_unaligned(self.ptr.cast()))^0x3030303030303030;let mask=x&0xf0f0f0f0f0f0f0f0;if mask!=0{self.fetch_ud8()}else{x=x.wrapping_mul(10).wrapping_add(x>>8)&0x00ff00ff00ff00ff;x=x.wrapping_mul(100).wrapping_add(x>>16)&0x0000ffff0000ffff;x=x.wrapping_mul(10000).wrapping_add(x>>32)&0xffffffff;let y=u16::from_le(ptr::read_unaligned(self.ptr.add(8).cast()))^0x3030;if y&0xf0f0==0{self.ptr=self.ptr.add(11);x as u32*100+((y.wrapping_mul(10).wrapping_add(y>>8))&0xff)as u32}else if y&0xf0==0{self.ptr=self.ptr.add(10);x as u32*10+(y&0xff)as u32}else{self.ptr=self.ptr.add(9);x as u32}}}}#[doc=" Appends `count` decimal integers to `values`, retaining its reserved capacity."]#[doc=""]#[doc=" # Safety"]#[doc=" The next `count` tokens must satisfy this reader's `u32` input requirements."]pub unsafe fn extend_u32(&mut self,values:&mut Vec<u32>,count:usize){values.reserve(count);let end=values.len()+count;unsafe{#[cfg(target_arch="x86_64")]if count>=544&&std::is_x86_feature_detected!("avx2"){self.extend_u32_avx2(values,count);}while values.len()<end{values.push(self.u32());}}}#[cfg(target_arch="x86_64")]#[target_feature(enable="avx2")]unsafe fn extend_u32_avx2(&mut self,values:&mut Vec<u32>,count:usize){use std::arch::x86_64::*;const CHUNK:usize=1<<17;const CAPACITY:usize=CHUNK/8+16;#[inline]#[target_feature(enable="avx2")]unsafe fn two_tokens(input:&mut*const u8)->__m256i{unsafe{let bytes=_mm256_loadu_si256((*input).cast());let separators=_mm256_movemask_epi8(_mm256_cmpgt_epi8(_mm256_set1_epi8(33),bytes))as u32;let first=separators.trailing_zeros()as usize;let second=(separators&(separators-1)).trailing_zeros()as usize;let windows=_mm256_inserti128_si256::<1>(bytes,_mm_loadu_si128((*input).add(first+1).cast()));let rows=_mm256_set_m128i(_mm_loadu_si128(FastInput::SHUFFLE.as_ptr().add(second-first-1).cast()),_mm_loadu_si128(FastInput::SHUFFLE.as_ptr().add(first).cast()));*input=(*input).add(second+1);let digits=_mm256_shuffle_epi8(_mm256_subs_epu8(windows,_mm256_set1_epi8(b'0' as i8)),rows);_mm256_madd_epi16(_mm256_maddubs_epi16(digits,_mm256_set1_epi16(0x010a)),_mm256_set1_epi32(0x00010064))}}unsafe{let start=values.len();let mut scratch=Vec::<u32>::with_capacity(3*CAPACITY);let scratch=scratch.as_mut_ptr();let mut written=0;while count-written>=544{let chunk=CHUNK.min(2*(count-written-32))&!3;let mut end=[self.ptr;4];for(k,end)in end.iter_mut().enumerate(){let mut p=self.ptr.add(chunk*(k+1)/4);while*p>b' '{p=p.add(1);}*end=p.add(1);}let mut input=[self.ptr,end[0],end[1],end[2]];let output=[values.as_mut_ptr().add(start+written),scratch,scratch.add(CAPACITY),scratch.add(2*CAPACITY)];let mut done=0;loop{let left=(0..4).map(|k|end[k].offset_from(input[k])).min().unwrap();if left<33{break;}for _ in 0..(left-32)/22+1{let g0=two_tokens(&mut input[0]);let g1=two_tokens(&mut input[1]);let g2=two_tokens(&mut input[2]);let g3=two_tokens(&mut input[3]);let k=_mm256_set1_epi32(0x00012710);let h01=_mm256_castsi256_ps(_mm256_madd_epi16(_mm256_packus_epi32(g0,g1),k));let h23=_mm256_castsi256_ps(_mm256_madd_epi16(_mm256_packus_epi32(g2,g3),k));let high=_mm256_castps_si256(_mm256_shuffle_ps::<0x88>(h01,h23));let low=_mm256_castps_si256(_mm256_shuffle_ps::<0xdd>(h01,h23));let v=_mm256_add_epi32(_mm256_mullo_epi32(high,_mm256_set1_epi32(100000000)),low);let q=_mm256_permutevar8x32_epi32(v,_mm256_setr_epi32(0,4,1,5,2,6,3,7));ptr::write_unaligned(output[0].add(done).cast::<u64>(),_mm256_extract_epi64::<0>(q)as u64);ptr::write_unaligned(output[1].add(done).cast::<u64>(),_mm256_extract_epi64::<1>(q)as u64);ptr::write_unaligned(output[2].add(done).cast::<u64>(),_mm256_extract_epi64::<2>(q)as u64);ptr::write_unaligned(output[3].add(done).cast::<u64>(),_mm256_extract_epi64::<3>(q)as u64);done+=2;}}let mut lengths=[done;4];for k in 0..4{self.ptr=input[k];while self.ptr<end[k]{output[k].add(lengths[k]).write(self.u32());lengths[k]+=1;}}written+=lengths[0];for k in 1..4{ptr::copy_nonoverlapping(output[k],values.as_mut_ptr().add(start+written),lengths[k]);written+=lengths[k];}self.ptr=end[3];}values.set_len(start+written);}}#[cfg(all(target_arch="x86_64",target_feature="ssse3"))]#[inline]pub unsafe fn u64(&mut self)->u64{unsafe{self.u64_simd::<20>()}}#[cfg(target_arch="x86_64")]const SHUFFLE:[u8;32]=const{let mut table=[128;32];let mut i=16;while i<32{table[i]=(i-16)as u8;i+=1;}table};#[cfg(all(target_arch="x86_64",target_feature="ssse3"))]#[inline]unsafe fn parse_ud16(digits:std::arch::x86_64::__m128i)->u64{use std::arch::x86_64::*;unsafe{let pairs=_mm_maddubs_epi16(digits,_mm_set1_epi16(0x010a));let quads=_mm_madd_epi16(pairs,_mm_set1_epi32(0x00010064));let octets=_mm_add_epi64(_mm_mul_epu32(quads,_mm_set1_epi64x(10000)),_mm_srli_epi64::<32>(quads));(_mm_cvtsi128_si64(octets)as u64)*100000000+(_mm_cvtsi128_si64(_mm_srli_si128::<8>(octets))as u64)}}#[cfg(all(target_arch="x86_64",target_feature="ssse3"))]#[inline]unsafe fn u64_simd<const MAX_DIGITS:usize>(&mut self)->u64{use std::arch::x86_64::*;unsafe{let mut digits=_mm_sub_epi8(_mm_loadu_si128(self.ptr.cast()),_mm_set1_epi8(b'0' as i8));let mask=_mm_movemask_epi8(digits)as u32;if mask!=0{let len=mask.trailing_zeros();digits=_mm_shuffle_epi8(digits,_mm_loadu_si128(Self::SHUFFLE.as_ptr().add(len as usize).cast()));self.ptr=self.ptr.add(len as usize+1);return Self::parse_ud16(digits);}self.ptr=self.ptr.add(16);let mut res=Self::parse_ud16(digits);let mut rem=ptr::read_unaligned(self.ptr.cast::<u32>())^0x30303030;if(rem&0xf0f0f0)==0{if MAX_DIGITS==19{res=res.wrapping_mul(1000).wrapping_add(((rem&0xff)as u64).wrapping_mul(100).wrapping_add((((rem.wrapping_mul(2561))&0xff0000)>>16)as u64));self.ptr=self.ptr.add(4);}else{let four=(rem&0xf0f0f0f0)==0;rem=rem.wrapping_shl((!four as u32)<<3);rem=rem.wrapping_mul(10).wrapping_add(rem>>8)&0x00ff00ff;rem=rem.wrapping_mul(100).wrapping_add(rem>>16)&0x0000ffff;res=res.wrapping_mul(1000+9000*four as u64).wrapping_add(rem as u64);self.ptr=self.ptr.add(4+four as usize);}}else if(rem&0xf0f0)==0{res=res.wrapping_mul(100).wrapping_add((((rem>>8).wrapping_add(rem.wrapping_mul(10)))&0xff)as u64);self.ptr=self.ptr.add(3);}else if(rem&0xf0)==0{res=res.wrapping_mul(10).wrapping_add((rem&0x0000000f)as u64);self.ptr=self.ptr.add(2);}else{self.ptr=self.ptr.add(1);}res}}#[cfg(not(all(target_arch="x86_64",target_feature="ssse3")))]#[inline]pub unsafe fn u64(&mut self)->u64{unsafe{let mut res;let mut x=ptr::read_unaligned(self.ptr as*const u64);x^=0x3030303030303030;if(x&0xf0f0f0f0f0f0f0f0)==0{self.ptr=self.ptr.add(8);let mut y=ptr::read_unaligned(self.ptr as*const u64);x=x.wrapping_mul(10).wrapping_add(x>>8)&0x00ff00ff00ff00ff;x=x.wrapping_mul(100).wrapping_add(x>>16)&0x0000ffff0000ffff;x=x.wrapping_mul(10000).wrapping_add(x>>32)&0x00000000ffffffff;res=x;y^=0x3030303030303030;if(y&0xf0f0f0f0f0f0f0f0)==0{self.ptr=self.ptr.add(8);y=y.wrapping_mul(10).wrapping_add(y>>8)&0x00ff00ff00ff00ff;y=y.wrapping_mul(100).wrapping_add(y>>16)&0x0000ffff0000ffff;y=y.wrapping_mul(10000).wrapping_add(y>>32)&0x00000000ffffffff;res=res.wrapping_mul(100000000).wrapping_add(y);let mut rem=ptr::read_unaligned(self.ptr as*const u32);rem^=0x30303030;if(rem&0xf0f0f0f0)==0{rem=rem.wrapping_mul(10).wrapping_add(rem>>8)&0x00ff00ff;rem=rem.wrapping_mul(100).wrapping_add(rem>>16)&0x0000ffff;res=res.wrapping_mul(10000).wrapping_add(rem as u64);self.ptr=self.ptr.add(5);}else if(rem&0xf0f0f0)==0{res=res.wrapping_mul(1000).wrapping_add(((rem&0xff)as u64).wrapping_mul(100).wrapping_add((((rem.wrapping_mul(2561))&0xff0000)>>16)as u64));self.ptr=self.ptr.add(4);}else if(rem&0xf0f0)==0{res=res.wrapping_mul(100).wrapping_add((((rem>>8).wrapping_add(rem.wrapping_mul(10)))&0xff)as u64);self.ptr=self.ptr.add(3);}else if(rem&0xf0)==0{res=res.wrapping_mul(10).wrapping_add((rem&0x0000000f)as u64);self.ptr=self.ptr.add(2);}else{self.ptr=self.ptr.add(1);}}else{let mut x=(y&0xffffffff)as u32;if(x&0xf0f0f0f0)==0{y>>=32;x=x.wrapping_mul(10).wrapping_add(x>>8)&0x00ff00ff;x=x.wrapping_mul(100).wrapping_add(x>>16)&0x0000ffff;res=res.wrapping_mul(10000).wrapping_add(x as u64);self.ptr=self.ptr.add(4);}let mut x=(y&0xffff)as u16;if(x&0xf0f0)==0{y>>=16;x=x.wrapping_mul(10).wrapping_add(x>>8)&0x00ff;res=res.wrapping_mul(100).wrapping_add(x as u64);self.ptr=self.ptr.add(2);}let x=(y&0xf0)==0;if x{res=res.wrapping_mul(10).wrapping_add(y&0xff);}self.ptr=self.ptr.add(x as usize+1);}}else{res=self.fetch_ud8()as u64;}res}}#[cfg(all(target_arch="x86_64",target_feature="ssse3"))]#[inline]pub unsafe fn u128(&mut self)->u128{use std::arch::x86_64::*;const POW10:[u64;16]=const{let mut powers=[1;16];let mut i=1;while i<16{powers[i]=powers[i-1]*10;i+=1;}powers};unsafe{let first=_mm_sub_epi8(_mm_loadu_si128(self.ptr.cast()),_mm_set1_epi8(b'0' as i8));let mask=_mm_movemask_epi8(first)as u32;if mask!=0{let len=mask.trailing_zeros()as usize;self.ptr=self.ptr.add(len+1);return Self::parse_ud16(_mm_shuffle_epi8(first,_mm_loadu_si128(Self::SHUFFLE.as_ptr().add(len).cast())))as u128;}let second=_mm_sub_epi8(_mm_loadu_si128(self.ptr.add(16).cast()),_mm_set1_epi8(b'0' as i8));let mask=_mm_movemask_epi8(second)as u32;if mask!=0{let len=mask.trailing_zeros()as usize;self.ptr=self.ptr.add(17+len);return Self::parse_ud16(first)as u128*POW10[len]as u128+Self::parse_ud16(_mm_shuffle_epi8(second,_mm_loadu_si128(Self::SHUFFLE.as_ptr().add(len).cast())))as u128;}let mut tail=ptr::read_unaligned(self.ptr.add(32).cast::<u64>())^0x3030303030303030;let len=(tail&0xf0f0f0f0f0f0f0f0).trailing_zeros()as usize/8;tail=if len==0{0}else{tail<<((8-len)*8)};tail=tail.wrapping_mul(10).wrapping_add(tail>>8)&0x00ff00ff00ff00ff;tail=tail.wrapping_mul(100).wrapping_add(tail>>16)&0x0000ffff0000ffff;tail=tail.wrapping_mul(10000).wrapping_add(tail>>32)&0xffffffff;self.ptr=self.ptr.add(33+len);(Self::parse_ud16(first)as u128*10_000_000_000_000_000+Self::parse_ud16(second)as u128)*POW10[len]as u128+tail as u128}}#[cfg(not(all(target_arch="x86_64",target_feature="ssse3")))]#[inline]pub unsafe fn u128(&mut self)->u128{unsafe{let mut res=0u128;for i in 0..4{let mut x=ptr::read_unaligned(self.ptr as*const u64);x^=0x3030303030303030;if(x&0xf0f0f0f0f0f0f0f0)!=0{break;}x=x.wrapping_mul(10).wrapping_add(x>>8)&0x00ff00ff00ff00ff;x=x.wrapping_mul(100).wrapping_add(x>>16)&0x0000ffff0000ffff;x=x.wrapping_mul(10000).wrapping_add(x>>32)&0x00000000ffffffff;if i==0{res=x as u128;}else{res=res.wrapping_mul(100000000).wrapping_add(x as u128);}self.ptr=self.ptr.add(8);}let mut res2=0u64;let mut pow=1u64;let mut x=ptr::read_unaligned(self.ptr as*const u64);x^=0x3030303030303030;let mut rem=x;if(x&0xf0f0f0f0)==0{rem>>=32;x=x.wrapping_mul(10).wrapping_add(x>>8)&0x00ff00ff;x=x.wrapping_mul(100).wrapping_add(x>>16)&0x0000ffff;res2=x;pow=10000;self.ptr=self.ptr.add(4);}{let mut x=(rem&0xffff)as u16;if(x&0xf0f0)==0{rem>>=16;x=x.wrapping_mul(10).wrapping_add(x>>8)&0x00ff;res2=res2.wrapping_mul(100).wrapping_add(x as u64);pow=pow.wrapping_mul(100);self.ptr=self.ptr.add(2);}}{let x=(rem&0xf0)==0;if x{res2=res2.wrapping_mul(10).wrapping_add(rem&0xff);pow=pow.wrapping_mul(10);}self.ptr=self.ptr.add(x as usize+1);}res=res.wrapping_mul(pow as u128).wrapping_add(res2 as u128);res}}#[inline]pub unsafe fn usize(&mut self)->usize{unsafe{self.u64()as usize}}#[inline]pub unsafe fn i8(&mut self)->i8{unsafe{let b=*self.ptr==b'-';self.ptr=self.ptr.add(b as usize);let mut x=self.u8()as i8;if b{x=x.wrapping_neg();}x}}#[inline]pub unsafe fn i16(&mut self)->i16{unsafe{let b=*self.ptr==b'-';self.ptr=self.ptr.add(b as usize);let mut x=self.u16()as i16;if b{x=x.wrapping_neg();}x}}#[inline]pub unsafe fn i32(&mut self)->i32{unsafe{let b=*self.ptr==b'-';self.ptr=self.ptr.add(b as usize);let mut x=self.u32()as i32;if b{x=x.wrapping_neg();}x}}#[inline]pub unsafe fn i64(&mut self)->i64{unsafe{let b=*self.ptr==b'-';self.ptr=self.ptr.add(b as usize);#[cfg(all(target_arch="x86_64",target_feature="ssse3"))]let mut x=self.u64_simd::<19>()as i64;#[cfg(not(all(target_arch="x86_64",target_feature="ssse3")))]let mut x=self.u64()as i64;if b{x=x.wrapping_neg();}x}}#[inline]pub unsafe fn i128(&mut self)->i128{unsafe{let b=*self.ptr==b'-';self.ptr=self.ptr.add(b as usize);let mut x=self.u128()as i128;if b{x=x.wrapping_neg();}x}}#[inline]pub unsafe fn isize(&mut self)->isize{unsafe{self.i64()as isize}}#[inline]pub unsafe fn byte(&mut self)->u8{unsafe{let c=*self.ptr;self.ptr=self.ptr.add(2);c}}#[inline]pub unsafe fn bytes<'a>(&mut self)->&'a[u8]{unsafe{let start=self.ptr;'token:{#[cfg(all(target_arch="x86_64",any(target_feature="avx2",target_feature="avx512bw")))]{let x=self.ptr.cast::<u64>().read_unaligned();if x.wrapping_sub(0x2121_2121_2121_2121)&!x&0x8080_8080_8080_8080!=0{break 'token;}}#[cfg(all(target_arch="x86_64",target_feature="avx512bw"))]{use std::arch::x86_64::*;let space=_mm512_set1_epi8(32);while self.end.offset_from(self.ptr)>=64{let bytes=_mm512_loadu_si512(self.ptr.cast());let low=_mm512_cmple_epu8_mask(bytes,space);if low!=0{self.ptr=self.ptr.add(low.trailing_zeros()as usize);break 'token;}self.ptr=self.ptr.add(64);}}#[cfg(all(target_arch="x86_64",target_feature="avx2",not(target_feature="avx512bw")))]{use std::arch::x86_64::*;let space=_mm256_set1_epi8(32);while self.end.offset_from(self.ptr)>=32{let bytes=_mm256_loadu_si256(self.ptr.cast());let low=_mm256_cmpeq_epi8(_mm256_min_epu8(bytes,space),bytes);if _mm256_movemask_epi8(low)!=0{break;}self.ptr=self.ptr.add(32);}}loop{let x=self.ptr.cast::<u64>().read_unaligned();if x.wrapping_sub(0x2121_2121_2121_2121)&!x&0x8080_8080_8080_8080!=0{break 'token;}self.ptr=self.ptr.add(8);}}while!(*self.ptr).is_ascii_whitespace(){self.ptr=self.ptr.add(1);}let len=self.ptr.offset_from(start)as usize;self.ptr=self.ptr.add(1);std::slice::from_raw_parts(start,len)}}#[inline]pub unsafe fn parse<T>(&mut self)->T where T:FromStr{unsafe{let s=std::str::from_utf8_unchecked(self.bytes());s.parse().ok().unwrap()}}}#[doc=" Buffered token reader with the same token requirements as [`FastInput`]."]#[doc=" Tokens may span reads and borrowed tokens remain valid until the next scan."]pub struct BufferedInput<R>{reader:R,buffer:Vec<u8>,input:FastInput<'static>,filled:usize,eof:bool}impl<R:Read>BufferedInput<R>{#[doc=" # Safety"]#[doc=" Every scan must satisfy [`FastInput`]'s token requirements, including UTF-8."]pub unsafe fn new(reader:R)->Self{let buffer=vec![b' ';(1<<16)+16];let input=FastInput{ptr:buffer.as_ptr(),end:buffer.as_ptr(),_marker:PhantomData};Self{reader,buffer,input,filled:0,eof:false}}#[cold]fn refill(&mut self)->bool{if self.eof{return false;}let position=unsafe{self.input.ptr.offset_from(self.buffer.as_ptr())as usize};self.buffer.copy_within(position..self.filled,0);self.filled-=position;self.input=FastInput{ptr:self.buffer.as_ptr(),end:self.buffer.as_ptr(),_marker:PhantomData};loop{if self.filled==self.buffer.len()-16{self.buffer.resize(2*self.filled+16,b' ');self.input=FastInput{ptr:self.buffer.as_ptr(),end:self.buffer.as_ptr(),_marker:PhantomData};}let end=self.buffer.len()-16;let start=self.filled;match self.reader.read(&mut self.buffer[self.filled..end]){Ok(0)=>{self.eof=true;if self.filled!=0{self.buffer[self.filled]=b' ';self.filled+=1;}}Ok(n)=>self.filled+=n,Err(e)if e.kind()==std::io::ErrorKind::Interrupted=>continue,Err(e)=>panic!("io error: {e}"),}let(prefix,chunks)=self.buffer[start..self.filled].as_rchunks();let end=prefix.len()+8*chunks.iter().rposition(|&chunk|{let x=u64::from_le_bytes(chunk);x.wrapping_sub(0x2121_2121_2121_2121)&!x&0x8080_8080_8080_8080!=0}).map_or(0,|i|i+1);if let Some(end)=self.buffer[start..start+end].iter().rposition(u8::is_ascii_whitespace){self.buffer[self.filled..self.filled+16].fill(b' ');self.input=FastInput{ptr:self.buffer.as_ptr(),end:unsafe{self.buffer.as_ptr().add(start+end+1)},_marker:PhantomData};return true;}if self.eof{self.input=FastInput{ptr:self.buffer.as_ptr(),end:self.buffer.as_ptr(),_marker:PhantomData};return false;}}}}macro_rules!impl_buffered_scan_integer{($($ty:ty,$read:ident,$method:ident);*$(;)?)=>{$(#[inline]fn$read(&mut self)->Option<$ty>{if self.input.ptr>=self.input.end&&!self.refill(){return None;}Some(unsafe{self.input.$method()})})*};}impl<R:Read>ScanSource for BufferedInput<R>{#[inline]fn skip_whitespace(&mut self){loop{self.input.skip_whitespace();if self.input.ptr<self.input.end||!self.refill(){break;}}}#[inline]fn next_token(&mut self)->Option<&str>{if self.input.ptr>=self.input.end&&!self.refill(){return None;}Some(unsafe{std::str::from_utf8_unchecked(self.input.bytes())})}impl_buffered_scan_integer!(u8,read_u8,u8;u16,read_u16,u16;u32,read_u32,u32;u64,read_u64,u64;u128,read_u128,u128;usize,read_usize,usize;i8,read_i8,i8;i16,read_i16,i16;i32,read_i32,i32;i64,read_i64,i64;i128,read_i128,i128;isize,read_isize,isize;);}static DIGIT4:[[u8;4];10000]=const{let mut arr=[[b' ';4];10000];let mut i=0;while i<10000{let mut x=i;let mut j=4;while j>0{j-=1;arr[i][j]=b'0'+(x%10)as u8;x/=10;}i+=1;}arr};static DIGIT4_TRIMMED:[u32;10000]=const{let mut arr=[0;10000];let mut i=0;while i<10000{let off=(i<10)as usize+(i<100)as usize+(i<1000)as usize;arr[i]=(u32::from_le_bytes(DIGIT4[i])>>(8*off))|(((3-off)as u32)<<30);i+=1;}arr};pub struct FastOutput<W>where W:Write{buf:Box<[u8]>,pos:usize,inner:W}impl FastOutput<File>{pub fn stdout()->Self{let mut stdout=stdout().lock();stdout.flush().unwrap();Self::new(File::from(stdout.as_fd().try_clone_to_owned().unwrap()))}}impl<W>Drop for FastOutput<W>where W:Write{fn drop(&mut self){let _=self.inner.write_all(&self.buf[..self.pos]);}}impl<W>FastOutput<W>where W:Write{pub fn new(writer:W)->Self{Self::with_capacity(1<<18,writer)}pub fn with_capacity(capacity:usize,writer:W)->Self{FastOutput{buf:vec![0;capacity.max(32)].into_boxed_slice(),pos:0,inner:writer}}pub fn flush(&mut self){self.flush_buf();self.inner.flush().unwrap();}#[cold]fn flush_buf(&mut self){if self.pos!=0{self.inner.write_all(&self.buf[..self.pos]).unwrap();self.pos=0;}}#[inline]fn ensure_capacity(&mut self,capacity:usize){if self.buf.len()-self.pos<capacity{self.flush_buf();}}#[inline]unsafe fn write_byte_unchecked(&mut self,byte:u8){unsafe{*self.buf.as_mut_ptr().add(self.pos)=byte;}self.pos+=1;}#[inline]unsafe fn write_digit4_unchecked(&mut self,x:usize){debug_assert!(x<10000);unsafe{ptr::write_unaligned(self.buf.as_mut_ptr().add(self.pos)as*mut u32,ptr::read_unaligned((DIGIT4.as_ptr()as*const u8).add(4*x)as*const u32));}self.pos+=4;}#[inline]unsafe fn write_digit4_trimmed_unchecked(&mut self,x:usize){unsafe{let word=*DIGIT4_TRIMMED.get_unchecked(x);ptr::write_unaligned(self.buf.as_mut_ptr().add(self.pos).cast::<u32>(),(word&0x3fffffff).to_le());self.pos+=(word>>30)as usize+1;}}#[inline]unsafe fn write_u8_unchecked(&mut self,x:u8){let off=(x<10)as usize+(x<100)as usize+1;unsafe{ptr::write_unaligned(self.buf.as_mut_ptr().add(self.pos)as*mut u32,ptr::read_unaligned((DIGIT4.as_ptr()as*const u8).add(4*x as usize+off)as*const u32));}self.pos+=4-off;}#[inline]unsafe fn write_u16_unchecked(&mut self,x:u16){unsafe{if x>=10000{self.write_digit4_trimmed_unchecked((x/10000)as usize);self.write_digit4_unchecked((x%10000)as usize);}else{self.write_digit4_trimmed_unchecked(x as usize);}}}#[inline]unsafe fn write_u32_unchecked(&mut self,x:u32){unsafe{if x>=1_0000_0000{let b=x/10000;let a=x/100000000;self.write_u8_unchecked(a as u8);self.write_digit4_unchecked((b-a*10000)as usize);self.write_digit4_unchecked((x%10000)as usize);}else if x>=10000{self.write_digit4_trimmed_unchecked((x/10000)as usize);self.write_digit4_unchecked((x%10000)as usize);}else{self.write_digit4_trimmed_unchecked(x as usize);}}}#[inline(always)]unsafe fn write_u64_unchecked(&mut self,x:u64){unsafe{if x<10000{self.write_digit4_trimmed_unchecked(x as usize);return;}if x>=1_0000_0000_0000_0000{let d=x/10000;let c=x/100000000;let b=x/1000000000000;let a=x/10000000000000000;self.write_digit4_trimmed_unchecked(a as usize);self.write_digit4_unchecked((b-a*10000)as usize);self.write_digit4_unchecked((c-b*10000)as usize);self.write_digit4_unchecked((d-c*10000)as usize);self.write_digit4_unchecked((x%10000)as usize);}else if x>=1_0000_0000_0000{let c=x/10000;let b=x/100000000;let a=x/1000000000000;self.write_digit4_trimmed_unchecked(a as usize);self.write_digit4_unchecked((b-a*10000)as usize);self.write_digit4_unchecked((c-b*10000)as usize);self.write_digit4_unchecked((x%10000)as usize);}else if x>=1_0000_0000{let b=x/10000;let a=x/100000000;self.write_digit4_trimmed_unchecked(a as usize);self.write_digit4_unchecked((b-a*10000)as usize);self.write_digit4_unchecked((x%10000)as usize);}else{self.write_digit4_trimmed_unchecked((x/10000)as usize);self.write_digit4_unchecked((x%10000)as usize);}}}#[inline]pub fn u8(&mut self,x:u8){self.ensure_capacity(4);unsafe{self.write_u8_unchecked(x)}}#[inline]pub fn u16(&mut self,x:u16){self.ensure_capacity(5);unsafe{self.write_u16_unchecked(x)}}#[inline]pub fn u32(&mut self,x:u32){self.ensure_capacity(10);unsafe{self.write_u32_unchecked(x)}}#[doc=" Writes each integer right-aligned in ten ASCII columns, followed by a space."]pub fn u32_slice_padded(&mut self,values:&[u32]){#[cfg(target_arch="x86_64")]let written=if self.buf.len()>=92&&std::is_x86_feature_detected!("avx2"){unsafe{self.u32_slice_padded_avx2(values)}}else{0};#[cfg(not(target_arch="x86_64"))]let written=0;for&value in&values[written..]{let len=value.checked_ilog10().map_or(1,|x|x as usize+1);self.bytes(&[b' ';9][..10-len]);self.u32(value);self.byte(b' ');}}#[cfg(target_arch="x86_64")]#[target_feature(enable="avx2")]unsafe fn u32_slice_padded_avx2(&mut self,values:&[u32])->usize{use std::arch::x86_64::*;#[inline]#[target_feature(enable="avx2")]unsafe fn divide<const MAGIC:i64,const SHIFT:i32>(x:__m256i)->__m256i{let m=_mm256_set1_epi64x(MAGIC);let even=_mm256_srli_epi64::<SHIFT>(_mm256_mul_epu32(x,m));let odd=_mm256_srli_epi64::<SHIFT>(_mm256_mul_epu32(_mm256_srli_epi64::<32>(x),m));_mm256_blend_epi32::<170>(even,_mm256_slli_epi64::<32>(odd))}#[inline]#[target_feature(enable="avx2")]unsafe fn two_digits(x:__m256i)->__m256i{let tens=_mm256_mulhi_epu16(x,_mm256_set1_epi16(6554));_mm256_sub_epi16(_mm256_slli_epi16::<8>(x),_mm256_mullo_epi16(tens,_mm256_set1_epi16(2559)))}#[inline]#[target_feature(enable="avx2")]unsafe fn text(digits:__m256i)->__m256i{let leading=_mm256_xor_si256(digits,_mm256_sub_epi64(digits,_mm256_set1_epi64x(1)));_mm256_blendv_epi8(_mm256_or_si256(digits,_mm256_set1_epi8(b'0' as i8)),_mm256_set1_epi8(b' ' as i8),leading)}#[inline]#[target_feature(enable="avx2")]unsafe fn divide8(p:*const u32)->(__m256i,__m256i){unsafe{let v=_mm256_loadu_si256(p.cast());let high=divide::<1374389535,37>(v);let top=divide::<1125899907,50>(v);let halves=_mm256_add_epi32(_mm256_slli_epi32::<16>(high),_mm256_mullo_epi32(top,_mm256_set1_epi32(1-10000*65536)));let remainder=_mm256_sub_epi32(v,_mm256_mullo_epi32(high,_mm256_set1_epi32(100)));let tail=_mm256_or_si256(two_digits(remainder),_mm256_set1_epi32(0x203030));let tiny=_mm256_cmpeq_epi32(_mm256_min_epu32(v,_mm256_set1_epi32(9)),v);let tail=_mm256_sub_epi32(tail,_mm256_and_si256(tiny,_mm256_set1_epi32(16)));(halves,tail)}}const fn mask(chunk:usize,source:usize)->[u8;32]{let mut mask=[128;32];let mut i=0;while i<32{let pos=chunk*16+i%16;let field=pos/11;let digit=pos%11;if field<4&&(if digit<8{field/2}else{2})==source{mask[i]=(if digit<8{field%2*8+digit}else{field*4+digit-8})as u8;}i+=1;}mask}#[inline]#[target_feature(enable="avx2")]unsafe fn shuffle<const C:usize,const S:usize>(v:__m256i)->__m256i{unsafe{_mm256_shuffle_epi8(v,_mm256_loadu_si256(const{mask(C,S)}.as_ptr().cast()))}}#[inline]#[target_feature(enable="avx2")]unsafe fn store8(p:*mut u8,halves:__m256i,tail:__m256i){unsafe{let hundreds={let q;std::arch::asm!("vpmulhuw {q}, {x}, {m}",q=lateout(ymm_reg)q,x=in(ymm_reg)halves,m=in(ymm_reg)_mm256_set1_epi16(5243),options(pure,nomem,nostack,preserves_flags),);_mm256_srli_epi16::<3>(q)};let rest=_mm256_sub_epi16(halves,_mm256_mullo_epi16(hundreds,_mm256_set1_epi16(100)));let lo=text(two_digits(_mm256_unpacklo_epi16(hundreds,rest)));let hi=text(two_digits(_mm256_unpackhi_epi16(hundreds,rest)));let c0=_mm256_or_si256(shuffle::<0,0>(lo),shuffle::<0,2>(tail));let c1=_mm256_or_si256(_mm256_or_si256(shuffle::<1,0>(lo),shuffle::<1,1>(hi)),shuffle::<1,2>(tail));let c2=_mm256_or_si256(shuffle::<2,1>(hi),shuffle::<2,2>(tail));_mm256_storeu_si256(p.add(60).cast(),c2);_mm256_storeu_si256(p.add(44).cast(),c1);_mm256_storeu_si256(p.add(28).cast(),c0);_mm_storeu_si128(p.cast(),_mm256_castsi256_si128(c0));_mm_storeu_si128(p.add(16).cast(),_mm256_castsi256_si128(c1));_mm_storel_epi64(p.add(32).cast(),_mm256_castsi256_si128(c2));ptr::write_unaligned(p.add(40).cast(),_mm_extract_epi32::<2>(_mm256_castsi256_si128(c2)));}}let count=values.len()/8*8;unsafe{let mut i=0;while i<count{self.ensure_capacity(92);let n=((self.buf.len()-self.pos-4)/88*8).min(count-i);let mut p=self.buf.as_mut_ptr().add(self.pos);let mut previous=divide8(values.as_ptr().add(i));for j in(8..n).step_by(8){let next=divide8(values.as_ptr().add(i+j));store8(p,previous.0,previous.1);previous=next;p=p.add(88);}store8(p,previous.0,previous.1);i+=n;self.pos+=n*11;}}count}#[inline(always)]pub fn u64(&mut self,x:u64){self.ensure_capacity(20);unsafe{self.write_u64_unchecked(x)}}#[inline]pub fn i8(&mut self,x:i8){if x<0{self.ensure_capacity(5);unsafe{self.write_byte_unchecked(b'-');self.write_u8_unchecked(x.wrapping_neg()as u8);}}else{self.u8(x as u8);}}#[inline]pub fn i16(&mut self,x:i16){if x<0{self.ensure_capacity(6);unsafe{self.write_byte_unchecked(b'-');self.write_u16_unchecked(x.wrapping_neg()as u16);}}else{self.u16(x as u16);}}#[inline]pub fn i32(&mut self,x:i32){if x<0{self.ensure_capacity(11);unsafe{self.write_byte_unchecked(b'-');self.write_u32_unchecked(x.wrapping_neg()as u32);}}else{self.u32(x as u32);}}#[inline(always)]pub fn i64(&mut self,x:i64){if x<0{self.ensure_capacity(21);unsafe{self.write_byte_unchecked(b'-');self.write_u64_unchecked(x.wrapping_neg()as u64);}}else{self.u64(x as u64);}}#[inline(always)]pub fn usize(&mut self,x:usize){if usize::BITS==64{self.u64(x as u64);}else{self.u32(x as u32);}}#[inline(always)]pub fn isize(&mut self,x:isize){if isize::BITS==64{self.i64(x as i64);}else{self.i32(x as i32);}}pub fn u128(&mut self,mut x:u128){const BASE:u128=10_000_000_000_000_000_000;let mut groups=[0u64;2];let mut len=0;while x>u64::MAX as u128{groups[len]=(x%BASE)as u64;x/=BASE;len+=1;}self.u64(x as u64);for&x in groups[..len].iter().rev(){self.ensure_capacity(19);unsafe{ptr::copy_nonoverlapping(DIGIT4[(x/10_000_000_000_000_000)as usize].as_ptr().add(1),self.buf.as_mut_ptr().add(self.pos),3);self.pos+=3;self.write_digit4_unchecked((x/1_000_000_000_000%10000)as usize);self.write_digit4_unchecked((x/100_000_000%10000)as usize);self.write_digit4_unchecked((x/10000%10000)as usize);self.write_digit4_unchecked((x%10000)as usize);}}}pub fn i128(&mut self,x:i128){if x<0{self.byte(b'-');}self.u128(x.unsigned_abs());}#[inline]pub fn byte(&mut self,b:u8){self.ensure_capacity(1);unsafe{self.write_byte_unchecked(b)}}#[inline(always)]pub fn bytes(&mut self,s:&[u8]){if s.len()>self.buf.len(){self.flush_buf();self.inner.write_all(s).unwrap();}else{self.ensure_capacity(s.len());unsafe{ptr::copy_nonoverlapping(s.as_ptr(),self.buf.as_mut_ptr().add(self.pos),s.len());}self.pos+=s.len();}}}impl<W:Write>fmt::Write for FastOutput<W>{fn write_str(&mut self,s:&str)->fmt::Result{self.bytes(s.as_bytes());Ok(())}}}
// codesnip-guard: _huge_pages
#[cfg_attr(any(),rustfmt::skip)]pub use self::huge_pages::advise_huge_pages;#[cfg_attr(any(),rustfmt::skip)]mod huge_pages{#[inline]pub fn advise_huge_pages<T>(_values:&mut Vec<T>){#[cfg(all(target_os="linux",target_arch="x86_64"))]unsafe{unsafe extern "C"{fn madvise(addr:*mut std::ffi::c_void,len:usize,advice:std::ffi::c_int)->std::ffi::c_int;}const PAGE_SIZE:usize=1<<12;const MADV_HUGEPAGE:std::ffi::c_int=14;let ptr=_values.as_mut_ptr().cast::<u8>();let offset=ptr.align_offset(PAGE_SIZE);let len=(_values.capacity()*size_of::<T>()).saturating_sub(offset)&!(PAGE_SIZE-1);if len>=1<<20{let _=madvise(ptr.add(offset).cast(),len,MADV_HUGEPAGE);}}}}
// codesnip-guard: _iter_print
#[cfg_attr(any(),rustfmt::skip)]pub use self::iter_print::IterPrint;#[cfg_attr(any(),rustfmt::skip)]mod iter_print{use std::{fmt::Display,io::{Error,Write}};pub trait IterPrint{fn iter_print<W,S>(self,writer:&mut W,sep:S,is_head:bool)->Result<(),Error>where W:Write,S:Display;}macro_rules!impl_iter_print_tuple{(@impl,)=>{impl IterPrint for(){fn iter_print<W,S>(self,_writer:&mut W,_sep:S,_is_head:bool)->Result<(),Error>where W:Write,S:Display{Ok(())}}};(@impl$($A:ident$a:ident)?,$($B:ident$b:ident)*)=>{impl<$($A,)?$($B),*>IterPrint for($($A,)?$($B),*)where$($A:Display,)?$($B:Display),*{fn iter_print<W,S>(self,writer:&mut W,sep:S,is_head:bool)->Result<(),Error>where W:Write,S:Display{let($($a,)?$($b,)*)=self;$(if is_head{::std::write!(writer,"{}",$a)?;}else{::std::write!(writer,"{}{}",sep,$a)?;})?$(::std::write!(writer,"{}{}",sep,$b)?;)*Ok(())}}};(@inc,,$C:ident$c:ident$($D:ident$d:ident)*)=>{impl_iter_print_tuple!(@impl,);impl_iter_print_tuple!(@inc$C$c,,$($D$d)*);};(@inc$A:ident$a:ident,$($B:ident$b:ident)*,$C:ident$c:ident$($D:ident$d:ident)*)=>{impl_iter_print_tuple!(@impl$A$a,$($B$b)*);impl_iter_print_tuple!(@inc$A$a,$($B$b)*$C$c,$($D$d)*);};(@inc$A:ident$a:ident,$($B:ident$b:ident)*,)=>{impl_iter_print_tuple!(@impl$A$a,$($B$b)*);};($($t:tt)*)=>{impl_iter_print_tuple!(@inc,,$($t)*);};}impl_iter_print_tuple!(A a B b C c D d E e F f G g H h I i J j K k);#[doc=" Print expressions with a separator."]#[doc=" - `iter_print!(writer, args...)`"]#[doc=" - `iter_print!(fast; writer, args...)`: use `FastOutput` and `FastPrint`"]#[doc=" - `@sep $expr`: set separator (default: `' '`)"]#[doc=" - `@ns`: alias for `@sep \"\"`"]#[doc=" - `@lf`: alias for `@sep '\\n'`"]#[doc=" - `@sp`: alias for `@sep ' '`"]#[doc=" - `@fmt ($lit, $($expr),*)`: print `format!($lit, $($expr),*)`"]#[doc=" - `@flush`: flush writer (auto insert `!`)"]#[doc=" - `@it $expr`: print iterator"]#[doc=" - `@padded_u32 $expr`: print a u32 slice in ten-column fields followed by spaces"]#[doc=" - `@it1 $expr`: print iterator as 1-indexed"]#[doc=" - `@cw ($char $expr)`: print iterator as `(elem as u8 + $char as u8) as char`"]#[doc=" - `@bw ($byte $expr)`: print iterator as `(elem as u8 + $byte) as char`"]#[doc=" - `@it2d $expr`: print 2d-iterator"]#[doc=" - `@tup $expr`: print tuple (need to import [`IterPrint`])"]#[doc=" - `@ittup $expr`: print iterative tuple (need to import [`IterPrint`])"]#[doc=" - `$expr`: print expr"]#[doc=" - `{ args... }`: scoped"]#[doc=" - `;`: print `'\\n'`"]#[doc=" - `!`: not print `'\\n'` at the end"]#[macro_export]macro_rules!iter_print{(@@fmt normal$writer:expr,$sep:expr,$is_head:expr,($lit:literal$(,$e:expr)*$(,)?))=>{if!$is_head{::std::write!($writer,"{}",$sep).expect("io error");}::std::write!($writer,$lit,$($e),*).expect("io error");};(@@fmt fast$writer:expr,$sep:expr,$is_head:expr,($lit:literal$(,$e:expr)*$(,)?))=>{{use::std::fmt::Write as _;if!$is_head{FastPrint::fast_print(&$sep,&mut$writer);}::std::write!($writer,$lit,$($e),*).expect("io error");}};(@@item normal$writer:expr,$sep:expr,$is_head:expr,$e:expr)=>{$crate::iter_print!(@@fmt normal$writer,$sep,$is_head,("{}",$e));};(@@item fast$writer:expr,$sep:expr,$is_head:expr,$e:expr)=>{if!$is_head{FastPrint::fast_print(&$sep,&mut$writer);}FastPrint::fast_print(&$e,&mut$writer);};(@@line_feed normal$writer:expr$(,)?)=>{::std::writeln!($writer).expect("io error");};(@@line_feed fast$writer:expr$(,)?)=>{$writer.byte(b'\n');};(@@flush normal$writer:expr)=>{{use::std::io::Write as _;$writer.flush().expect("io error");}};(@@flush fast$writer:expr)=>{$writer.flush();};(@@it fast$writer:expr,$sep:expr,$is_head:expr,$iter:expr)=>{{match$iter.into_iter(){mut iter=>{if let::std::option::Option::Some(first)=iter.next(){{let item=first;$crate::iter_print!(@@item fast$writer,$sep,$is_head,item);}for item in iter{$crate::iter_print!(@@item fast$writer,$sep,false,item);}}}}}};(@@it$mode:ident$writer:expr,$sep:expr,$is_head:expr,$iter:expr)=>{{let mut iter=$iter.into_iter();if let Some(item)=iter.next(){$crate::iter_print!(@@item$mode$writer,$sep,$is_head,item);}for item in iter{$crate::iter_print!(@@item$mode$writer,$sep,false,item);}}};(@@padded_u32 fast$writer:expr,$sep:expr,$is_head:expr,$values:expr)=>{{if!$is_head{FastPrint::fast_print(&$sep,&mut$writer);}$writer.u32_slice_padded(&$values);}};(@@padded_u32 normal$writer:expr,$sep:expr,$is_head:expr,$values:expr)=>{{if!$is_head{::std::write!($writer,"{}",$sep).expect("io error");}let values=&$values;let values:&[u32]=values.as_ref();for value in values{::std::write!($writer,"{value:10} ").expect("io error");}}};(@@it1$mode:ident$writer:expr,$sep:expr,$is_head:expr,$iter:expr)=>{{let mut iter=$iter.into_iter();if let Some(item)=iter.next(){$crate::iter_print!(@@item$mode$writer,$sep,$is_head,item+1);}for item in iter{$crate::iter_print!(@@item$mode$writer,$sep,false,item+1);}}};(@@cw$mode:ident$writer:expr,$sep:expr,$is_head:expr,($ch:literal$iter:expr))=>{{let mut iter=$iter.into_iter();let b=$ch as u8;if let Some(item)=iter.next(){$crate::iter_print!(@@item$mode$writer,$sep,$is_head,(item as u8+b)as char);}for item in iter{$crate::iter_print!(@@item$mode$writer,$sep,false,(item as u8+b)as char);}}};(@@bw$mode:ident$writer:expr,$sep:expr,$is_head:expr,($b:literal$iter:expr))=>{{let mut iter=$iter.into_iter();let b:u8=$b;if let Some(item)=iter.next(){$crate::iter_print!(@@item$mode$writer,$sep,$is_head,(item as u8+b)as char);}for item in iter{$crate::iter_print!(@@item$mode$writer,$sep,false,(item as u8+b)as char);}}};(@@it2d fast$writer:expr,$sep:expr,$is_head:expr,$iter:expr)=>{for(i,item)in$iter.into_iter().enumerate(){if i>0{$crate::iter_print!(@@line_feed fast$writer);}$crate::iter_print!(@@it fast$writer,$sep,i>0||$is_head,item);}};(@@it2d$mode:ident$writer:expr,$sep:expr,$is_head:expr,$iter:expr)=>{let mut iter=$iter.into_iter();if let Some(item)=iter.next(){$crate::iter_print!(@@it$mode$writer,$sep,$is_head,item);}for item in iter{$crate::iter_print!(@@line_feed$mode$writer);$crate::iter_print!(@@it$mode$writer,$sep,true,item);}};(@@tup normal$writer:expr,$sep:expr,$is_head:expr,$tuple:expr)=>{IterPrint::iter_print($tuple,&mut$writer,$sep,$is_head).expect("io error");};(@@tup fast$writer:expr,$sep:expr,$is_head:expr,$tuple:expr)=>{FastIterPrint::fast_iter_print($tuple,&mut$writer,$sep,$is_head);};(@@ittup$mode:ident$writer:expr,$sep:expr,$is_head:expr,$iter:expr)=>{let mut iter=$iter.into_iter();if let Some(item)=iter.next(){$crate::iter_print!(@@tup$mode$writer,$sep,$is_head,item);}for item in iter{$crate::iter_print!(@@line_feed$mode$writer);$crate::iter_print!(@@tup$mode$writer,$sep,true,item);}};(@@assert_tag item)=>{};(@@assert_tag it)=>{};(@@assert_tag padded_u32)=>{};(@@assert_tag it1)=>{};(@@assert_tag it2d)=>{};(@@assert_tag tup)=>{};(@@assert_tag ittup)=>{};(@@assert_tag$tag:ident)=>{::std::compile_error!(::std::concat!("invalid tag in `iter_print!`: `",std::stringify!($tag),"`"));};(@@inner$mode:ident$writer:expr,$sep:expr,$is_head:expr,@sep$e:expr,$($t:tt)*)=>{$crate::iter_print!(@@inner$mode$writer,$e,$is_head,$($t)*);};(@@inner fast$writer:expr,$sep:expr,$is_head:expr,@ns$($t:tt)*)=>{$crate::iter_print!(@@inner fast$writer,(),$is_head,$($t)*);};(@@inner$mode:ident$writer:expr,$sep:expr,$is_head:expr,@ns$($t:tt)*)=>{$crate::iter_print!(@@inner$mode$writer,"",$is_head,$($t)*);};(@@inner$mode:ident$writer:expr,$sep:expr,$is_head:expr,@lf$($t:tt)*)=>{$crate::iter_print!(@@inner$mode$writer,'\n',$is_head,$($t)*);};(@@inner$mode:ident$writer:expr,$sep:expr,$is_head:expr,@sp$($t:tt)*)=>{$crate::iter_print!(@@inner$mode$writer,' ',$is_head,$($t)*);};(@@inner$mode:ident$writer:expr,$sep:expr,$is_head:expr,@flush$($t:tt)*)=>{$crate::iter_print!(@@flush$mode$writer);$crate::iter_print!(@@inner$mode$writer,$sep,$is_head,!$($t)*);};(@@inner$mode:ident$writer:expr,$sep:expr,$is_head:expr,@fmt$arg:tt$($t:tt)*)=>{$crate::iter_print!(@@fmt$mode$writer,$sep,$is_head,$arg);$crate::iter_print!(@@inner$mode$writer,$sep,$is_head,$($t)*);};(@@inner$mode:ident$writer:expr,$sep:expr,$is_head:expr,@cw$arg:tt$($t:tt)*)=>{$crate::iter_print!(@@cw$mode$writer,$sep,$is_head,$arg);$crate::iter_print!(@@inner$mode$writer,$sep,$is_head,$($t)*);};(@@inner$mode:ident$writer:expr,$sep:expr,$is_head:expr,@bw$arg:tt$($t:tt)*)=>{$crate::iter_print!(@@bw$mode$writer,$sep,$is_head,$arg);$crate::iter_print!(@@inner$mode$writer,$sep,$is_head,$($t)*);};(@@inner$mode:ident$writer:expr,$sep:expr,$is_head:expr,@$tag:ident$e:expr,$($t:tt)*)=>{$crate::iter_print!(@@assert_tag$tag);$crate::iter_print!(@@$tag$mode$writer,$sep,$is_head,$e);$crate::iter_print!(@@inner$mode$writer,$sep,false,$($t)*);};(@@inner$mode:ident$writer:expr,$sep:expr,$is_head:expr,@$tag:ident$e:expr;$($t:tt)*)=>{$crate::iter_print!(@@assert_tag$tag);$crate::iter_print!(@@$tag$mode$writer,$sep,$is_head,$e);$crate::iter_print!(@@line_feed$mode$writer);$crate::iter_print!(@@inner$mode$writer,$sep,true,$($t)*);};(@@inner$mode:ident$writer:expr,$sep:expr,$is_head:expr,@$tag:ident$e:expr)=>{$crate::iter_print!(@@assert_tag$tag);$crate::iter_print!(@@$tag$mode$writer,$sep,$is_head,$e);$crate::iter_print!(@@inner$mode$writer,$sep,false,);};(@@inner$mode:ident$writer:expr,$sep:expr,$is_head:expr,@$tag:ident$($t:tt)*)=>{::std::compile_error!(::std::concat!("invalid expr in `iter_print!`: `",std::stringify!($($t)*),"`"));};(@@inner$mode:ident$writer:expr,$sep:expr,$is_head:expr,,$($t:tt)*)=>{$crate::iter_print!(@@inner$mode$writer,$sep,$is_head,$($t)*);};(@@inner$mode:ident$writer:expr,$sep:expr,$is_head:expr,;$($t:tt)*)=>{$crate::iter_print!(@@line_feed$mode$writer);$crate::iter_print!(@@inner$mode$writer,$sep,$is_head,$($t)*);};(@@inner$mode:ident$writer:expr,$sep:expr,$is_head:expr,!$(,)?)=>{};(@@inner$mode:ident$writer:expr,$sep:expr,$is_head:expr,!$($t:tt)*)=>{$crate::iter_print!(@@inner$mode$writer,$sep,$is_head,$($t)*);};(@@inner$mode:ident$writer:expr,$sep:expr,$is_head:expr,)=>{$crate::iter_print!(@@line_feed$mode$writer);};(@@inner$mode:ident$writer:expr,$sep:expr,$is_head:expr,{$($t:tt)*}$($rest:tt)*)=>{$crate::iter_print!(@@inner$mode$writer,$sep,$is_head,$($t)*,!);$crate::iter_print!(@@inner$mode$writer,$sep,$is_head,$($rest)*);};(@@inner$mode:ident$writer:expr,$sep:expr,$is_head:expr,$($t:tt)*)=>{$crate::iter_print!(@@inner$mode$writer,$sep,$is_head,@item$($t)*);};(fast;$writer:expr,$($t:tt)*)=>{{$crate::iter_print!(@@inner fast$writer,' ',true,$($t)*);}};($writer:expr,$($t:tt)*)=>{{$crate::iter_print!(@@inner normal$writer,' ',true,$($t)*);}};}}
// codesnip-guard: array
#[cfg_attr(any(),rustfmt::skip)]mod array{#[macro_export]macro_rules!array{[@inner$data:ident=[$init:expr;$len:expr]]=>{{use::std::mem::{ManuallyDrop,MaybeUninit};let mut$data:[MaybeUninit<_>;$len]=unsafe{MaybeUninit::uninit().assume_init()};$init;#[repr(C)]union __Transmuter<const N:usize,T:Clone>{src:ManuallyDrop<[MaybeUninit<T>;N]>,dst:ManuallyDrop<[T;N]>,}ManuallyDrop::into_inner(unsafe{__Transmuter{src:ManuallyDrop::new($data)}.dst})}};[||$e:expr;$len:expr]=>{$crate::array![@inner data=[data.iter_mut().for_each(|item|*item=MaybeUninit::new($e));$len]]};[|$i:pat_param|$e:expr;$len:expr]=>{$crate::array![@inner data=[data.iter_mut().enumerate().for_each(|($i,item)|*item=MaybeUninit::new($e));$len]]};[$e:expr;$len:expr]=>{{let e=$e;$crate::array![||Clone::clone(&e);$len]}};}}
// codesnip-guard: scanner
#[cfg_attr(any(),rustfmt::skip)]pub use self::scanner::*;#[cfg_attr(any(),rustfmt::skip)]mod scanner{use std::{iter::{FromIterator,from_fn,repeat_with},marker::PhantomData};pub fn read_stdin_all()->String{use std::io::Read as _;let mut s=String::new();std::io::stdin().read_to_string(&mut s).expect("io error");s}pub fn read_stdin_all_unchecked()->String{use std::io::Read as _;let mut buf=Vec::new();std::io::stdin().read_to_end(&mut buf).expect("io error");unsafe{String::from_utf8_unchecked(buf)}}pub fn read_all(mut reader:impl std::io::Read)->String{let mut s=String::new();reader.read_to_string(&mut s).expect("io error");s}pub fn read_all_unchecked(mut reader:impl std::io::Read)->String{let mut buf=Vec::new();reader.read_to_end(&mut buf).expect("io error");unsafe{String::from_utf8_unchecked(buf)}}pub fn read_stdin_line()->String{let mut s=String::new();std::io::stdin().read_line(&mut s).expect("io error");s}pub trait Scan:Sized{type Output;fn scan<S:ScanSource>(source:&mut S)->Option<Self::Output>;fn scan_vec<S:ScanSource>(source:&mut S,size:usize,capacity:usize)->Vec<Self::Output>{let mut values=Vec::with_capacity(capacity.max(size));values.extend((0..size).map(|_|source.scan::<Self>()));values}}pub trait MarkedScan:Sized{type Output;fn mscan<S:ScanSource>(self,source:&mut S)->Option<Self::Output>;}pub trait ScanSource:Sized{#[doc=" Reads a token under the source's input requirements."]#[doc=" Checked sources return `None` at EOF; unchecked sources require available input."]fn next_token(&mut self)->Option<&str>;#[doc=" Skips separators without consuming the next token."]#[inline]fn skip_whitespace(&mut self){}#[inline]fn read_u8(&mut self)->Option<u8>{self.next_token()?.parse().ok()}#[inline]fn read_u16(&mut self)->Option<u16>{self.next_token()?.parse().ok()}#[inline]fn read_u32(&mut self)->Option<u32>{self.next_token()?.parse().ok()}fn read_u32_vec(&mut self,size:usize,capacity:usize)->Vec<u32>{let mut values=Vec::with_capacity(capacity.max(size));values.extend((0..size).map(|_|self.scan::<u32>()));values}#[inline]fn read_u64(&mut self)->Option<u64>{self.next_token()?.parse().ok()}#[inline]fn read_u128(&mut self)->Option<u128>{self.next_token()?.parse().ok()}#[inline]fn read_usize(&mut self)->Option<usize>{self.next_token()?.parse().ok()}#[inline]fn read_i8(&mut self)->Option<i8>{self.next_token()?.parse().ok()}#[inline]fn read_i16(&mut self)->Option<i16>{self.next_token()?.parse().ok()}#[inline]fn read_i32(&mut self)->Option<i32>{self.next_token()?.parse().ok()}#[inline]fn read_i64(&mut self)->Option<i64>{self.next_token()?.parse().ok()}#[inline]fn read_i128(&mut self)->Option<i128>{self.next_token()?.parse().ok()}#[inline]fn read_isize(&mut self)->Option<isize>{self.next_token()?.parse().ok()}#[doc=" Panics if reading fails."]#[inline]fn scan<T:Scan>(&mut self)->T::Output{T::scan(self).expect("scan error")}#[doc=" Panics if reading fails."]#[inline]fn mscan<T:MarkedScan>(&mut self,marker:T)->T::Output{marker.mscan(self).expect("scan error")}fn scan_vec<T:Scan>(&mut self,size:usize,capacity:usize)->Vec<T::Output>{if size==0{self.skip_whitespace();}T::scan_vec(self,size,capacity)}#[inline]fn iter<T:Scan>(&mut self)->ScannerIter<'_,Self,T>{ScannerIter{inner:self,_marker:PhantomData}}}#[derive(Clone,Debug)]pub struct Scanner<'a,I:Iterator<Item=&'a str>=std::str::SplitAsciiWhitespace<'a>>{iter:I}impl<'a>Scanner<'a>{pub fn new(s:&'a str)->Self{Self{iter:s.split_ascii_whitespace()}}}impl<'a,I:Iterator<Item=&'a str>>Scanner<'a,I>{pub fn new_from_iter(iter:I)->Self{Self{iter}}}impl<'a,I:Iterator<Item=&'a str>>ScanSource for Scanner<'a,I>{fn next_token(&mut self)->Option<&str>{self.iter.next()}}macro_rules!impl_scan{($($t:ty)*)=>{$(impl Scan for$t{type Output=Self;fn scan<I:ScanSource>(iter:&mut I)->Option<Self>{iter.next_token()?.parse::<$t>().ok()}})*};}impl_scan!(char f32 f64 String);macro_rules!impl_integer_scan{($($t:ty=>$read:ident),*$(,)?)=>{$(impl Scan for$t{type Output=Self;#[inline]fn scan<S:ScanSource>(source:&mut S)->Option<Self>{source.$read()}})*};}impl_integer_scan!(u8=>read_u8,u16=>read_u16,u64=>read_u64,u128=>read_u128,usize=>read_usize,i8=>read_i8,i16=>read_i16,i32=>read_i32,i64=>read_i64,i128=>read_i128,isize=>read_isize,);impl Scan for u32{type Output=Self;#[inline]fn scan<S:ScanSource>(source:&mut S)->Option<Self>{source.read_u32()}fn scan_vec<S:ScanSource>(source:&mut S,size:usize,capacity:usize)->Vec<Self>{source.read_u32_vec(size,capacity)}}macro_rules!impl_scan_tuple{(@impl$($T:ident)*)=>{impl<$($T:Scan),*>Scan for($($T,)*){type Output=($(<$T as Scan>::Output,)*);fn scan<It:ScanSource>(_iter:&mut It)->Option<Self::Output>{Some(($(<$T as Scan>::scan(_iter)?,)*))}}};(@inner$($T:ident)*,)=>{impl_scan_tuple!(@impl$($T)*);};(@inner$($T:ident)*,$U:ident$($Rest:ident)*)=>{impl_scan_tuple!(@impl$($T)*);impl_scan_tuple!(@inner$($T)*$U,$($Rest)*);};($($T:ident)*)=>{impl_scan_tuple!(@inner,$($T)*);};}impl_scan_tuple!(A B C D E F G H I J K);pub struct ScannerIter<'a,S,T>{inner:&'a mut S,_marker:PhantomData<fn()->T>}impl<S:ScanSource,T:Scan>Iterator for ScannerIter<'_,S,T>{type Item=T::Output;#[inline]fn next(&mut self)->Option<Self::Item>{T::scan(self.inner)}}#[doc=" scan a value with Scanner"]#[doc=""]#[doc=" - `scan_value!(scanner, ELEMENT)`"]#[doc=""]#[doc=" ELEMENT :="]#[doc=" - `$ty`: Scan"]#[doc=" - `&str`: borrowed token; the source stays borrowed until its last use"]#[doc=" - `@$expr`: MarkedScan"]#[doc=" - `$ty = $expr`: MarkedScan"]#[doc=" - `[ELEMENT; $expr]`: vector"]#[doc=" - `[$ty; $len; capacity $capacity]`: vector with reserved capacity"]#[doc=" - `[ELEMENT; const $expr]`: array"]#[doc=" - `[ELEMENT]`: iterator"]#[doc=" - `[ELEMENT; iter $expr]`: iterator of the specified length"]#[doc=" - `($(ELEMENT)*,)`: tuple"]#[macro_export]macro_rules!scan_value{(@repeat$scanner:expr,[$($t:tt)*]$len:expr)=>{{$crate::scan_value!(@iter$scanner,[$($t)*]$len).collect::<Vec<_>>()}};(@repeat$scanner:expr,[$($t:tt)*])=>{{::std::iter::repeat_with(||$crate::scan_value!(@inner$scanner,[]$($t)*))}};(@iter$scanner:expr,[$($t:tt)*]$len:expr)=>{{let size=$len;if size==0{$scanner.skip_whitespace();}$crate::scan_value!(@repeat$scanner,[$($t)*]).take(size)}};(@array$scanner:expr,[$($t:tt)*]$len:expr)=>{{if$len==0{$scanner.skip_whitespace();}$crate::array![||$crate::scan_value!(@inner$scanner,[]$($t)*);$len]}};(@tuple$scanner:expr,[$([$($args:tt)*])*])=>{($($($args)*,)*)};(@sparen$scanner:expr,[]@$e:expr;$($t:tt)*)=>{$crate::scan_value!(@sparen$scanner,[@$e]$($t)*)};(@sparen$scanner:expr,[]($($tt:tt)*);$($t:tt)*)=>{$crate::scan_value!(@sparen$scanner,[($($tt)*)]$($t)*)};(@sparen$scanner:expr,[][$($tt:tt)*];$($t:tt)*)=>{$crate::scan_value!(@sparen$scanner,[[$($tt)*]]$($t)*)};(@sparen$scanner:expr,[]$ty:ty=$e:expr;$($t:tt)*)=>{$crate::scan_value!(@sparen$scanner,[$ty=$e]$($t)*)};(@sparen$scanner:expr,[]$ty:ty;$($t:tt)*)=>{$crate::scan_value!(@sparen$scanner,[$ty]$($t)*)};(@sparen$scanner:expr,[]$($args:tt)*)=>{$crate::scan_value!(@repeat$scanner,[$($args)*])};(@sparen$scanner:expr,[$($args:tt)+]const$len:expr)=>{$crate::scan_value!(@array$scanner,[$($args)+]$len)};(@sparen$scanner:expr,[$($args:tt)+]iter$len:expr)=>{$crate::scan_value!(@iter$scanner,[$($args)+]$len)};(@sparen$scanner:expr,[$($args:tt)+]$len:expr;capacity$capacity:expr)=>{{let size=$len;let capacity=$capacity;$scanner.scan_vec::<$($args)+>(size,capacity)}};(@sparen$scanner:expr,[$($args:tt)+]$len:expr)=>{$crate::scan_value!(@repeat$scanner,[$($args)+]$len)};(@$tag:ident$scanner:expr,[[$($args:tt)*]])=>{$($args)*};(@$tag:ident$scanner:expr,[$($args:tt)*]@$e:expr$(,$($t:tt)*)?)=>{$crate::scan_value!(@$tag$scanner,[$($args)*[$scanner.mscan($e)]]$(,$($t)*)?)};(@$tag:ident$scanner:expr,[$($args:tt)*]($($tuple:tt)*)$($t:tt)*)=>{$crate::scan_value!(@$tag$scanner,[$($args)*[$crate::scan_value!(@tuple$scanner,[]$($tuple)*)]]$($t)*)};(@$tag:ident$scanner:expr,[$($args:tt)*][$($tt:tt)*]$($t:tt)*)=>{$crate::scan_value!(@$tag$scanner,[$($args)*[$crate::scan_value!(@sparen$scanner,[]$($tt)*)]]$($t)*)};(@$tag:ident$scanner:expr,[$($args:tt)*]&str$(,$($t:tt)*)?)=>{$crate::scan_value!(@$tag$scanner,[$($args)*[$scanner.next_token().expect("scan error")]]$(,$($t)*)?)};(@$tag:ident$scanner:expr,[$($args:tt)*]$ty:ty=$e:expr$(,$($t:tt)*)?)=>{$crate::scan_value!(@$tag$scanner,[$($args)*[{let _tmp:$ty=$scanner.mscan($e);_tmp}]]$(,$($t)*)?)};(@$tag:ident$scanner:expr,[$($args:tt)*]$ty:ty$(,$($t:tt)*)?)=>{$crate::scan_value!(@$tag$scanner,[$($args)*[$scanner.scan::<$ty>()]]$(,$($t)*)?)};(@$tag:ident$scanner:expr,[$($args:tt)*],$($t:tt)*)=>{$crate::scan_value!(@$tag$scanner,[$($args)*]$($t)*)};(@$tag:ident$scanner:expr,[$($args:tt)*])=>{::std::compile_error!(::std::stringify!($($args)*))};(src=$src:expr,$($t:tt)*)=>{{let mut __scanner=Scanner::new($src);$crate::scan_value!(@inner __scanner,[]$($t)*)}};(iter=$iter:expr,$($t:tt)*)=>{{let mut __scanner=Scanner::new_from_iter($iter);$crate::scan_value!(@inner __scanner,[]$($t)*)}};($scanner:expr,$($t:tt)*)=>{$crate::scan_value!(@inner$scanner,[]$($t)*)}}#[doc=" scan and bind values with Scanner"]#[doc=""]#[doc=" - `scan!(scanner, $($pat $(: ELEMENT)?),*)`"]#[macro_export]macro_rules!scan{(@assert$p:pat)=>{};(@assert$($p:tt)*)=>{::std::compile_error!(::std::concat!("expected pattern, found `",::std::stringify!($($p)*),"`"));};(@pat$scanner:expr,[][])=>{};(@pat$scanner:expr,[][],$($t:tt)*)=>{$crate::scan!(@pat$scanner,[][]$($t)*)};(@pat$scanner:expr,[$($p:tt)*][]$x:ident$($t:tt)*)=>{$crate::scan!(@pat$scanner,[$($p)*$x][]$($t)*)};(@pat$scanner:expr,[$($p:tt)*][]::$($t:tt)*)=>{$crate::scan!(@pat$scanner,[$($p)*::][]$($t)*)};(@pat$scanner:expr,[$($p:tt)*][]&$($t:tt)*)=>{$crate::scan!(@pat$scanner,[$($p)*&][]$($t)*)};(@pat$scanner:expr,[$($p:tt)*][]($($x:tt)*)$($t:tt)*)=>{$crate::scan!(@pat$scanner,[$($p)*($($x)*)][]$($t)*)};(@pat$scanner:expr,[$($p:tt)*][][$($x:tt)*]$($t:tt)*)=>{$crate::scan!(@pat$scanner,[$($p)*[$($x)*]][]$($t)*)};(@pat$scanner:expr,[$($p:tt)*][]{$($x:tt)*}$($t:tt)*)=>{$crate::scan!(@pat$scanner,[$($p)*{$($x)*}][]$($t)*)};(@pat$scanner:expr,[$($p:tt)*][]:$($t:tt)*)=>{$crate::scan!(@ty$scanner,[$($p)*][]$($t)*)};(@pat$scanner:expr,[$($p:tt)*][]$($t:tt)*)=>{$crate::scan!(@let$scanner,[$($p)*][usize]$($t)*)};(@ty$scanner:expr,[$($p:tt)*][$($tt:tt)*]@$e:expr$(,$($t:tt)*)?)=>{$crate::scan!(@let$scanner,[$($p)*][$($tt)*@$e]$(,$($t)*)?)};(@ty$scanner:expr,[$($p:tt)*][$($tt:tt)*]($($x:tt)*)$($t:tt)*)=>{$crate::scan!(@let$scanner,[$($p)*][$($tt)*($($x)*)]$($t)*)};(@ty$scanner:expr,[$($p:tt)*][$($tt:tt)*][$($x:tt)*]$($t:tt)*)=>{$crate::scan!(@let$scanner,[$($p)*][$($tt)*[$($x)*]]$($t)*)};(@ty$scanner:expr,[$($p:tt)*][$($tt:tt)*]&str$(,$($t:tt)*)?)=>{$crate::scan!(@let$scanner,[$($p)*][$($tt)*&str]$(,$($t)*)?)};(@ty$scanner:expr,[$($p:tt)*][$($tt:tt)*]$ty:ty=$e:expr$(,$($t:tt)*)?)=>{$crate::scan!(@let$scanner,[$($p)*][$($tt)*$ty=$e]$(,$($t)*)?)};(@ty$scanner:expr,[$($p:tt)*][$($tt:tt)*]$ty:ty$(,$($t:tt)*)?)=>{$crate::scan!(@let$scanner,[$($p)*][$($tt)*$ty]$(,$($t)*)?)};(@let$scanner:expr,[$($p:tt)*][$($tt:tt)*]$($t:tt)*)=>{$crate::scan!{@assert$($p)*}let$($p)* =$crate::scan_value!($scanner,$($tt)*);$crate::scan!(@pat$scanner,[][]$($t)*)};(src=$src:expr,$($t:tt)*)=>{let mut __scanner=Scanner::new($src);$crate::scan!(@pat __scanner,[][]$($t)*)};(iter=$iter:expr,$($t:tt)*)=>{let mut __scanner=Scanner::new_from_iter($iter);$crate::scan!(@pat __scanner,[][]$($t)*)};($scanner:expr,$($t:tt)*)=>{$crate::scan!(@pat$scanner,[][]$($t)*)}}#[doc=" define enum scan rules"]#[doc=""]#[doc=" # Example"]#[doc=" ```rust"]#[doc=" # use competitive::{define_enum_scan, tools::{CharsWithBase, Scan, ScanSource, Scanner, Usize1}};"]#[doc=" define_enum_scan! {"]#[doc="   enum Query: u8 {"]#[doc="     0 => Noop,"]#[doc="     1 => Args { i: Usize1, s: char },"]#[doc="     9 => Complex { n: usize, c: [(usize, Vec<usize> = CharsWithBase('a')); n] },"]#[doc="   }"]#[doc=" }"]#[doc=" ```"]#[macro_export]macro_rules!define_enum_scan{(@field_ty@repeat[$($t:tt)*]$($len:expr)?)=>{Vec<$crate::define_enum_scan!(@field_ty$($t)*)>};(@field_ty@array[$($t:tt)*]$len:expr)=>{[$crate::define_enum_scan!(@field_ty$($t)*);$len]};(@field_ty@tuple[$([$($args:tt)*])*])=>{($($($args)*,)*)};(@field_ty@sparen[]($($tt:tt)*);$($t:tt)*)=>{$crate::define_enum_scan!(@field_ty@sparen[($($tt)*)]$($t)*)};(@field_ty@sparen[][$($tt:tt)*];$($t:tt)*)=>{$crate::define_enum_scan!(@field_ty@sparen[[$($tt)*]]$($t)*)};(@field_ty@sparen[]$ty:ty=$e:expr;$($t:tt)*)=>{$crate::define_enum_scan!(@field_ty@sparen[$ty=$e]$($t)*)};(@field_ty@sparen[]$ty:ty;$($t:tt)*)=>{$crate::define_enum_scan!(@field_ty@sparen[$ty]$($t)*)};(@field_ty@sparen[]$($args:tt)*)=>{$crate::define_enum_scan!(@field_ty@repeat[$($args)*])};(@field_ty@sparen[$($args:tt)+]const$len:expr)=>{$crate::define_enum_scan!(@field_ty@array[$($args)+]$len)};(@field_ty@sparen[$($args:tt)+]$len:expr)=>{$crate::define_enum_scan!(@field_ty@repeat[$($args)+]$len)};(@field_ty@$tag:ident[$($args:tt)*]($($tuple:tt)*)$($t:tt)*)=>{$crate::define_enum_scan!(@field_ty@$tag[$($args)*[$crate::define_enum_scan!(@field_ty@tuple[]$($tuple)*)]]$($t)*)};(@field_ty@$tag:ident[$($args:tt)*][$($tt:tt)*]$($t:tt)*)=>{$crate::define_enum_scan!(@field_ty@$tag[$($args)*[$crate::define_enum_scan!(@field_ty@sparen[]$($tt)*)]]$($t)*)};(@field_ty@$tag:ident[$($args:tt)*]$ty:ty=$e:expr$(,$($t:tt)*)?)=>{$crate::define_enum_scan!(@field_ty@$tag[$($args)*[$ty]]$(,$($t)*)?)};(@field_ty@$tag:ident[$($args:tt)*]$ty:ty$(,$($t:tt)*)?)=>{$crate::define_enum_scan!(@field_ty@$tag[$($args)*[<$ty as Scan>::Output]]$(,$($t)*)?)};(@field_ty@$tag:ident[$($args:tt)*],$($t:tt)*)=>{$crate::define_enum_scan!(@field_ty@$tag[$($args)*]$($t)*)};(@field_ty@$tag:ident[[$($args:tt)*]])=>{$($args)*};(@field_ty@$tag:ident[$($args:tt)*])=>{::std::compile_error!(::std::stringify!($($args)*))};(@field_ty$($t:tt)*)=>{$crate::define_enum_scan!(@field_ty@inner[]$($t)*)};(@tag_expr raw,$iter:ident)=>{ScanSource::next_token($iter)?};(@tag_expr$d:ty,$iter:ident)=>{<$d as Scan>::scan($iter)?};(@variant([$($attr:tt)*]$vis:vis$T:ident$d:tt)[$($vars:tt)*])=>{$crate::define_enum_scan!{@def$($attr)*$vis enum$T:$d{$($vars)*}}};(@variant$ctx:tt[$($vars:tt)*]$p:pat=>$v:ident{$($fs:tt)*}$($rest:tt)*)=>{$crate::define_enum_scan!{@field$ctx[$($vars)*]$p=>$v[]$($fs)*;$($rest)*}};(@variant$ctx:tt[$($vars:tt)*]$p:pat=>$v:ident$($rest:tt)*)=>{$crate::define_enum_scan!{@variant$ctx[$($vars)*$p=>$v,]$($rest)*}};(@variant$ctx:tt[$($vars:tt)*],$($rest:tt)*)=>{$crate::define_enum_scan!{@variant$ctx[$($vars)*]$($rest)*}};(@endfield$ctx:tt[$($vars:tt)*]$p:pat=>$v:ident[$($fs:tt)*][$f:ident:$($spec:tt)*],$($rest:tt)*)=>{$crate::define_enum_scan!{@field$ctx[$($vars)*]$p=>$v[$($fs)*[$f:$($spec)*]]$($rest)*}};(@endfield$ctx:tt[$($vars:tt)*]$p:pat=>$v:ident[$($fs:tt)*][$f:ident:$($spec:tt)*];$($rest:tt)*)=>{$crate::define_enum_scan!{@variant$ctx[$($vars)*$p=>$v{$($fs)*[$f:$($spec)*]},]$($rest)*}};(@field$ctx:tt[$($vars:tt)*]$p:pat=>$v:ident[$($fs:tt)*];$($rest:tt)*)=>{$crate::define_enum_scan!{@variant$ctx[$($vars)*$p=>$v{$($fs)*},]$($rest)*}};(@field$ctx:tt[$($vars:tt)*]$p:pat=>$v:ident[$($fs:tt)*]$f:ident:($($tuple:tt)*)$sep:tt$($rest:tt)*)=>{$crate::define_enum_scan!{@endfield$ctx[$($vars)*]$p=>$v[$($fs)*][$f:($($tuple)*)]$sep$($rest)*}};(@field$ctx:tt[$($vars:tt)*]$p:pat=>$v:ident[$($fs:tt)*]$f:ident:[$($x:tt)*]$sep:tt$($rest:tt)*)=>{$crate::define_enum_scan!{@endfield$ctx[$($vars)*]$p=>$v[$($fs)*][$f:[$($x)*]]$sep$($rest)*}};(@field$ctx:tt[$($vars:tt)*]$p:pat=>$v:ident[$($fs:tt)*]$f:ident:$ty:ty=$e:expr,$($rest:tt)*)=>{$crate::define_enum_scan!{@endfield$ctx[$($vars)*]$p=>$v[$($fs)*][$f:$ty=$e],$($rest)*}};(@field$ctx:tt[$($vars:tt)*]$p:pat=>$v:ident[$($fs:tt)*]$f:ident:$ty:ty;$($rest:tt)*)=>{$crate::define_enum_scan!{@endfield$ctx[$($vars)*]$p=>$v[$($fs)*][$f:$ty];$($rest)*}};(@field$ctx:tt[$($vars:tt)*]$p:pat=>$v:ident[$($fs:tt)*]$f:ident:$ty:ty=$e:expr;$($rest:tt)*)=>{$crate::define_enum_scan!{@endfield$ctx[$($vars)*]$p=>$v[$($fs)*][$f:$ty=$e];$($rest)*}};(@field$ctx:tt[$($vars:tt)*]$p:pat=>$v:ident[$($fs:tt)*]$f:ident:$ty:ty,$($rest:tt)*)=>{$crate::define_enum_scan!{@endfield$ctx[$($vars)*]$p=>$v[$($fs)*][$f:$ty],$($rest)*}};(@def$(#[$attr:meta])*$vis:vis enum$T:ident:$d:tt{$($p:pat=>$v:ident$({$([$f:ident:$($spec:tt)*])*})?,)*})=>{$(#[$attr])*$vis enum$T{$($v$({$($f:$crate::define_enum_scan!(@field_ty$($spec)*)),*})?),*}impl Scan for$T{type Output=Self;fn scan<I:ScanSource>(iter:&mut I)->Option<Self>{let tag=$crate::define_enum_scan!(@tag_expr$d,iter);match tag{$($p=>{$($(let$f=$crate::scan_value!((*iter),$($spec)*);)*)?Some($T::$v$({$($f),*})?)}),*_=>None,}}}};($(#[$attr:meta])*$vis:vis enum$T:ident:raw{$($body:tt)*})=>{$crate::define_enum_scan!{@variant([$(#[$attr])*]$vis$T raw)[]$($body)*}};($(#[$attr:meta])*$vis:vis enum$T:ident:$d:ty{$($body:tt)*})=>{$crate::define_enum_scan!{@variant([$(#[$attr])*]$vis$T$d)[]$($body)*}};}#[derive(Debug,Copy,Clone)]pub enum Usize1{}impl Scan for Usize1{type Output=usize;fn scan<I:ScanSource>(iter:&mut I)->Option<Self::Output>{<usize as Scan>::scan(iter)?.checked_sub(1)}}#[derive(Debug,Copy,Clone)]pub struct CharWithBase(pub char);impl MarkedScan for CharWithBase{type Output=usize;fn mscan<I:ScanSource>(self,iter:&mut I)->Option<Self::Output>{Some((<char as Scan>::scan(iter)?as u8-self.0 as u8)as usize)}}#[derive(Debug,Copy,Clone)]pub enum Chars{}impl Scan for Chars{type Output=Vec<char>;fn scan<I:ScanSource>(iter:&mut I)->Option<Self::Output>{Some(iter.next_token()?.chars().collect())}}#[derive(Debug,Copy,Clone)]pub struct CharsWithBase(pub char);impl MarkedScan for CharsWithBase{type Output=Vec<usize>;fn mscan<I:ScanSource>(self,iter:&mut I)->Option<Self::Output>{Some(iter.next_token()?.chars().map(|c|(c as u8-self.0 as u8)as usize).collect())}}#[derive(Debug,Copy,Clone)]pub enum Byte1{}impl Scan for Byte1{type Output=u8;fn scan<I:ScanSource>(iter:&mut I)->Option<Self::Output>{let bytes=iter.next_token()?.as_bytes();assert_eq!(bytes.len(),1);Some(bytes[0])}}#[derive(Debug,Copy,Clone)]pub struct ByteWithBase(pub u8);impl MarkedScan for ByteWithBase{type Output=usize;fn mscan<I:ScanSource>(self,iter:&mut I)->Option<Self::Output>{Some((<char as Scan>::scan(iter)?as u8-self.0)as usize)}}#[derive(Debug,Copy,Clone)]pub enum Bytes{}impl Scan for Bytes{type Output=Vec<u8>;fn scan<I:ScanSource>(iter:&mut I)->Option<Self::Output>{Some(iter.next_token()?.bytes().collect())}}#[derive(Debug,Copy,Clone)]pub struct BytesWithBase(pub u8);impl MarkedScan for BytesWithBase{type Output=Vec<usize>;fn mscan<I:ScanSource>(self,iter:&mut I)->Option<Self::Output>{Some(iter.next_token()?.bytes().map(|c|(c-self.0)as usize).collect())}}#[derive(Debug,Copy,Clone)]pub struct Collect<T,B=Vec<<T as Scan>::Output>>where T:Scan,B:FromIterator<<T as Scan>::Output>{size:usize,_marker:PhantomData<fn()->(T,B)>}impl<T,B>Collect<T,B>where T:Scan,B:FromIterator<<T as Scan>::Output>{pub fn new(size:usize)->Self{Self{size,_marker:PhantomData}}}impl<T,B>MarkedScan for Collect<T,B>where T:Scan,B:FromIterator<<T as Scan>::Output>{type Output=B;fn mscan<I:ScanSource>(self,iter:&mut I)->Option<Self::Output>{if self.size==0{iter.skip_whitespace();}repeat_with(| |<T as Scan>::scan(iter)).take(self.size).collect()}}#[derive(Debug,Copy,Clone)]pub struct SizedCollect<T,B=Vec<<T as Scan>::Output>>where T:Scan,B:FromIterator<<T as Scan>::Output>{_marker:PhantomData<fn()->(T,B)>}impl<T,B>Scan for SizedCollect<T,B>where T:Scan,B:FromIterator<<T as Scan>::Output>{type Output=B;fn scan<I:ScanSource>(iter:&mut I)->Option<Self::Output>{let size=usize::scan(iter)?;if size==0{iter.skip_whitespace();}repeat_with(| |<T as Scan>::scan(iter)).take(size).collect()}}#[derive(Debug,Copy,Clone)]pub struct Splitted<T,P>where T:Scan{pat:P,_marker:PhantomData<fn()->T>}impl<T,P>Splitted<T,P>where T:Scan{pub fn new(pat:P)->Self{Self{pat,_marker:PhantomData}}}impl<T>MarkedScan for Splitted<T,char>where T:Scan{type Output=Vec<<T as Scan>::Output>;fn mscan<I:ScanSource>(self,iter:&mut I)->Option<Self::Output>{let mut iter=Scanner::new_from_iter(iter.next_token()?.split(self.pat));Some(from_fn(| |<T as Scan>::scan(&mut iter)).collect())}}impl<T>MarkedScan for Splitted<T,&str>where T:Scan{type Output=Vec<<T as Scan>::Output>;fn mscan<I:ScanSource>(self,iter:&mut I)->Option<Self::Output>{let mut iter=Scanner::new_from_iter(iter.next_token()?.split(self.pat));Some(from_fn(| |<T as Scan>::scan(&mut iter)).collect())}}impl<T,F>MarkedScan for F where F:Fn(&str)->Option<T>{type Output=T;fn mscan<I:ScanSource>(self,iter:&mut I)->Option<Self::Output>{self(iter.next_token()?)}}}