// codesnip-guard: SuffixArray
#[cfg_attr(any(),rustfmt::skip)]pub use self::suffix_array::SuffixArray;#[cfg_attr(any(),rustfmt::skip)]mod suffix_array{use std::ops::Index;#[derive(Clone,Debug)]pub struct SuffixArray{sa:Vec<usize>}impl SuffixArray{pub fn new<T>(text:&[T])->Self where T:Ord{let n=text.len();let mut ord:Vec<_>=(0..n).collect();ord.sort_unstable_by_key(|&i|&text[i]);let mut s=vec![0usize;n+1];let mut upper=0usize;for(k,&i)in ord.iter().enumerate(){if k==0||text[ord[k-1]]!=text[i]{upper+=1;}s[i]=upper;}s[n]=0;let sa=sa_is(&s,upper);Self{sa}}pub fn into_inner(self)->Vec<usize>{self.sa}pub fn lcp_array_with_rank<T>(&self,text:&[T])->(Vec<usize>,Vec<usize>)where T:PartialEq{let n=self.sa.len()-1;let mut rank=vec![0usize;n+1];for i in 0..=n{rank[self.sa[i]]=i;}let mut h=0usize;let mut lcp_array=vec![0usize;n];for i in 0..n{let r=rank[i]-1;let j=self.sa[r];while i+h<n&&j+h<n&&text[i+h]==text[j+h]{h+=1;}lcp_array[r]=h;h=h.saturating_sub(1);}(lcp_array,rank)}pub fn lcp_array<T>(&self,text:&[T])->Vec<usize>where T:PartialEq{self.lcp_array_with_rank(text).0}}impl Index<usize>for SuffixArray{type Output=usize;fn index(&self,index:usize)->&Self::Output{&self.sa[index]}}fn induced_sort(s:&[usize],upper:usize,is_s:&[bool],lms:&[usize])->Vec<usize>{let n=s.len();let mut sa=vec![!0usize;n];let mut bucket_size=vec![0usize;upper+1];for&c in s{bucket_size[c]+=1;}let mut bucket_tail=vec![0usize;upper+1];{let mut sum=0usize;for i in 0..=upper{sum+=bucket_size[i];bucket_tail[i]=sum;}}for&pos in lms.iter().rev(){let c=s[pos];bucket_tail[c]-=1;sa[bucket_tail[c]]=pos;}let mut bucket_head=vec![0usize;upper+1];{let mut sum=0usize;for i in 0..=upper{bucket_head[i]=sum;sum+=bucket_size[i];}}for i in 0..n{let v=sa[i];if v==!0||v==0{continue;}let p=v-1;if!is_s[p]{let c=s[p];sa[bucket_head[c]]=p;bucket_head[c]+=1;}}let mut bucket_tail=vec![0usize;upper+1];{let mut sum=0usize;for i in 0..=upper{sum+=bucket_size[i];bucket_tail[i]=sum;}}for i in(0..n).rev(){let v=sa[i];if v==!0||v==0{continue;}let p=v-1;if is_s[p]{let c=s[p];bucket_tail[c]-=1;sa[bucket_tail[c]]=p;}}sa}fn sa_is(s:&[usize],upper:usize)->Vec<usize>{let n=s.len();match n{0=>return vec![],1=>return vec![0],_=>{}}let mut is_s=vec![false;n];is_s[n-1]=true;for i in(0..n-1).rev(){is_s[i]=if s[i]<s[i+1]{true}else if s[i]>s[i+1]{false}else{is_s[i+1]};}let mut lms_map=vec![!0;n];let mut lms=vec![];for i in 1..n{if is_s[i]&&!is_s[i-1]{lms_map[i]=lms.len();lms.push(i);}}let mut sa=induced_sort(s,upper,&is_s,&lms);if lms.len()>1{let mut rec_s=vec![0usize;lms.len()];let mut rec_upper=0usize;let mut prev=!0usize;for&pos in&sa{if pos!=!0&&lms_map[pos]!=!0{if prev!=!0{let mut offset=0usize;loop{if s[prev+offset]!=s[pos+offset]||is_s[prev+offset]!=is_s[pos+offset]{rec_upper+=1;break;}if offset!=0{let prev_is_lms=lms_map[prev+offset]!=!0;let pos_is_lms=lms_map[pos+offset]!=!0;if prev_is_lms||pos_is_lms{rec_upper+=(prev_is_lms!=pos_is_lms)as usize;break;}}offset+=1;}}rec_s[lms_map[pos]]=rec_upper;prev=pos;}}let rec_sa=if rec_upper+1==lms.len(){let mut rec_sa=vec![0usize;lms.len()];for i in 0..lms.len(){rec_sa[rec_s[i]]=i;}rec_sa}else{sa_is(&rec_s,rec_upper)};let mut ordered_lms=Vec::with_capacity(lms.len());for&i in&rec_sa{ordered_lms.push(lms[i]);}sa=induced_sort(s,upper,&is_s,&ordered_lms);}sa}}
// codesnip-guard: binary_search
#[cfg_attr(any(),rustfmt::skip)]pub use self::binary_search::{Bisect,SliceBisectExt,binary_search,parallel_binary_search};#[cfg_attr(any(),rustfmt::skip)]mod binary_search{use std::cmp::Ordering;#[doc=" binary search helper"]pub trait Bisect:Clone{#[doc=" Return between two elements if search is not end."]fn bisect_middle_point(&self,other:&Self)->Option<Self>;}macro_rules!impl_bisect_unsigned{($($t:ty)*)=>{$(impl Bisect for$t{fn bisect_middle_point(&self,other:&Self)->Option<Self>{if self.abs_diff(*other)>1{Some(self.midpoint(*other))}else{None}}})*};}macro_rules!impl_bisect_signed{($($t:ty)*)=>{$(impl Bisect for$t{fn bisect_middle_point(&self,other:&Self)->Option<Self>{if self.signum()!=other.signum(){if match self.cmp(other){Ordering::Less=>self+1<*other,Ordering::Equal=>false,Ordering::Greater=>other+1<*self,}{Some((*self).midpoint(*other))}else{None}}else{if self.abs_diff(*other)>1{Some(self.midpoint(*other))}else{None}}}})*};}macro_rules!impl_bisect_float{($({$t:ident$u:ident$i:ident$e:expr})*)=>{$(impl Bisect for$t{fn bisect_middle_point(&self,other:&Self)->Option<Self>{fn to_float_ord(x:$t)->$i{let a=x.to_bits()as$i;a^(((a>>$e)as$u)>>1)as$i}fn from_float_ord(a:$i)->$t{$t::from_bits((a^(((a>>$e)as$u)>>1)as$i)as _)}<$i as Bisect>::bisect_middle_point(&to_float_ord(*self),&to_float_ord(*other)).map(from_float_ord)}})*};}impl_bisect_unsigned!(u8 u16 u32 u64 u128 usize);impl_bisect_signed!(i8 i16 i32 i64 i128 isize);impl_bisect_float!({f32 u32 i32 31}{f64 u64 i64 63});#[doc=" binary search for monotone segment"]#[doc=""]#[doc=" if `ok < err` then search [ok, err) where t(`ok`), t, t, .... t, t(`ret`), f,  ... f, f, f, `err`"]#[doc=""]#[doc=" if `err < ok` then search (err, ok] where `err`, f, f, f, ... f, t(`ret`), ... t, t, t(`ok`)"]pub fn binary_search<T,F>(mut f:F,mut ok:T,mut err:T)->T where T:Bisect,F:FnMut(&T)->bool{while let Some(m)=ok.bisect_middle_point(&err){if f(&m){ok=m;}else{err=m;}}ok}#[doc=" binary search for slice"]pub trait SliceBisectExt<T>{#[doc=" Returns the first element that satisfies a predicate."]fn find_bisect(&self,f:impl FnMut(&T)->bool)->Option<&T>;#[doc=" Returns the last element that satisfies a predicate."]fn rfind_bisect(&self,f:impl FnMut(&T)->bool)->Option<&T>;#[doc=" Returns the first index that satisfies a predicate."]#[doc=" if not found, returns `len()`."]fn position_bisect(&self,f:impl FnMut(&T)->bool)->usize;#[doc=" Returns the last index+1 that satisfies a predicate."]#[doc=" if not found, returns `0`."]fn rposition_bisect(&self,f:impl FnMut(&T)->bool)->usize;}impl<T>SliceBisectExt<T>for[T]{fn find_bisect(&self,f:impl FnMut(&T)->bool)->Option<&T>{self.get(self.position_bisect(f))}fn rfind_bisect(&self,f:impl FnMut(&T)->bool)->Option<&T>{let pos=self.rposition_bisect(f);if pos==0{None}else{self.get(pos-1)}}fn position_bisect(&self,mut f:impl FnMut(&T)->bool)->usize{binary_search(|i|f(&self[*i as usize]),self.len()as i64,-1)as usize}fn rposition_bisect(&self,mut f:impl FnMut(&T)->bool)->usize{binary_search(|i|f(&self[i-1]),0,self.len()+1)}}pub fn parallel_binary_search<T,F,G>(mut f:F,q:usize,ok:T,err:T)->Vec<T>where T:Bisect,F:FnMut(&[Option<T>])->G,G:Fn(usize)->bool{let mut ok=vec![ok;q];let mut err=vec![err;q];loop{let m:Vec<_>=ok.iter().zip(&err).map(|(ok,err)|ok.bisect_middle_point(err)).collect();if m.iter().all(|m|m.is_none()){break;}let g=f(&m);for(i,m)in m.into_iter().enumerate(){if let Some(m)=m{if g(i){ok[i]=m;}else{err[i]=m;}}}}ok}}