// codesnip-guard: SuffixTree
#[cfg_attr(any(),rustfmt::skip)]pub use self::suffix_tree::{MultipleSuffixTree,SuffixTree};#[cfg_attr(any(),rustfmt::skip)]mod suffix_tree{use super::SuffixArray;use std::ops::Range;#[derive(Clone,Debug,Eq,PartialEq,Ord,PartialOrd)]pub enum Delimited<T>{Separator(usize),Value(T)}#[derive(Debug)]pub struct STNode{pub parent:usize,pub depth:usize,pub sa_range:Range<usize>,pub child_index:Range<usize>,pub head:usize,pub pos:usize}pub struct SuffixTree<T>where T:Ord{text:Vec<T>,suffix_array:Vec<usize>,lcp_array:Vec<usize>,rank:Vec<usize>,nodes:Vec<STNode>,children:Vec<usize>,leafs:Vec<usize>,inv:Vec<usize>}struct Link{first_child:usize,last_child:usize,next_sibling:usize,prev_sibling:usize}struct SuffixTreeBuilder{nodes:Vec<STNode>,links:Vec<Link>}impl SuffixTreeBuilder{fn with_capacity(capacity:usize)->Self{Self{nodes:Vec::with_capacity(capacity),links:Vec::with_capacity(capacity)}}fn push_node(&mut self,depth:usize,start:usize)->usize{let node_id=self.nodes.len();self.nodes.push(STNode{parent:!0,depth,sa_range:start..!0,child_index:0..0,head:!0,pos:!0});self.links.push(Link{first_child:!0,last_child:!0,next_sibling:!0,prev_sibling:!0});node_id}fn attach_child(&mut self,parent:usize,child:usize){self.nodes[child].parent=parent;let tail=self.links[parent].last_child;if tail==!0{self.links[parent].first_child=child;}else{self.links[tail].next_sibling=child;self.links[child].prev_sibling=tail;}self.links[parent].last_child=child;}fn detach_last_child(&mut self,parent:usize,child:usize){let prev=self.links[child].prev_sibling;if prev==!0{self.links[parent].first_child=!0;}else{self.links[prev].next_sibling=!0;}self.links[parent].last_child=prev;self.links[child].prev_sibling=!0;self.links[child].next_sibling=!0;}fn reindex(&mut self,leafs:&mut[usize]){let mut new_index=vec![!0;self.nodes.len()];let mut stack=vec![0];let mut index=0;while let Some(node_id)=stack.pop(){new_index[node_id]=index;index+=1;let mut child=self.links[node_id].last_child;while child!=!0{stack.push(child);child=self.links[child].prev_sibling;}}for node in&mut self.nodes{if node.parent!=!0{node.parent=new_index[node.parent];}}for link in&mut self.links{if link.first_child!=!0{link.first_child=new_index[link.first_child];}if link.last_child!=!0{link.last_child=new_index[link.last_child];}if link.next_sibling!=!0{link.next_sibling=new_index[link.next_sibling];}if link.prev_sibling!=!0{link.prev_sibling=new_index[link.prev_sibling];}}for leaf in leafs{*leaf=new_index[*leaf];}for i in 0..self.nodes.len(){while new_index[i]!=i{let j=new_index[i];self.nodes.swap(i,j);self.links.swap(i,j);new_index.swap(i,j);}}}fn build_aux(&mut self,children:&[usize])->Vec<usize>{let n=self.nodes.len();let mut sub_size=vec![1usize;n];let mut heavy=vec![!0usize;n];for node in(0..n).rev(){let mut max_size=0usize;for&child in&children[self.nodes[node].child_index.clone()]{sub_size[node]+=sub_size[child];if sub_size[child]>max_size{max_size=sub_size[child];heavy[node]=child;}}}let mut inv=vec![0usize;n];let mut cur=0usize;let mut stack=vec![(0usize,0usize)];while let Some((v,h))=stack.pop(){let mut u=v;while u!=!0{self.nodes[u].head=h;self.nodes[u].pos=cur;inv[cur]=u;cur+=1;for&child in&children[self.nodes[u].child_index.clone()]{if child!=heavy[u]{stack.push((child,child));}}u=heavy[u];}}inv}fn build_children(&mut self)->Vec<usize>{let mut children=vec![!0;self.nodes.len()-1];let mut index=0;for node_id in 0..self.nodes.len(){let mut child=self.links[node_id].first_child;self.nodes[node_id].child_index.start=index;while child!=!0{children[index]=child;index+=1;child=self.links[child].next_sibling;}self.nodes[node_id].child_index.end=index;}children}}impl<T>SuffixTree<T>where T:Ord{pub fn new(text:Vec<T>)->Self{let n=text.len();let suffix_array=SuffixArray::new(&text);let(lcp_array,rank)=suffix_array.lcp_array_with_rank(&text);let mut builder=SuffixTreeBuilder::with_capacity(n*2);builder.push_node(0,0);let mut leafs=vec![!0;n+1];leafs[0]=0;let mut stack=Vec::with_capacity(n);stack.push(0);for i in 1..=n{let lcp=lcp_array[i-1];let mut last_popped=!0;while builder.nodes[stack.last().cloned().unwrap()].depth>lcp{last_popped=stack.pop().unwrap();builder.nodes[last_popped].sa_range.end=i;}if builder.nodes[stack.last().cloned().unwrap()].depth<lcp{let parent=stack.last().cloned().unwrap();let internal=builder.nodes.len();builder.push_node(lcp,builder.nodes[last_popped].sa_range.start);builder.detach_last_child(parent,last_popped);builder.attach_child(parent,internal);builder.attach_child(internal,last_popped);stack.push(internal);}let parent=stack.last().cloned().unwrap();let leaf=builder.nodes.len();builder.push_node(n-suffix_array[i],i);builder.attach_child(parent,leaf);stack.push(leaf);leafs[i]=leaf;}while let Some(node)=stack.pop(){builder.nodes[node].sa_range.end=n+1;}builder.reindex(&mut leafs[1..]);let children=builder.build_children();let inv=builder.build_aux(&children);let nodes=builder.nodes;let suffix_array=suffix_array.into_inner();Self{text,suffix_array,lcp_array,rank,nodes,children,leafs,inv}}pub fn text(&self)->&[T]{&self.text}pub fn suffix_array(&self)->&[usize]{&self.suffix_array}pub fn lcp_array(&self)->&[usize]{&self.lcp_array}pub fn rank(&self)->&[usize]{&self.rank}pub fn node_size(&self)->usize{self.nodes.len()}pub fn node(&self,node_id:usize)->&STNode{&self.nodes[node_id]}pub fn children(&self,node_id:usize)->&[usize]{&self.children[self.nodes[node_id].child_index.clone()]}pub fn depth_range(&self,node_id:usize)->Range<usize>{let node=&self.nodes[node_id];if node.parent==!0{0..0}else{self.nodes[node.parent].depth+1..node.depth+1}}pub fn kth_substrings(&self)->KthSubstrings<'_,T>{KthSubstrings::new(self)}fn node_covering_depth(&self,leaf:usize,depth:usize)->usize{debug_assert!(depth>0);debug_assert!(depth<=self.nodes[leaf].depth);let mut v=leaf;loop{let h=self.nodes[v].head;let parent=self.nodes[h].parent;let parent_depth=if parent==!0{0}else{self.nodes[parent].depth};if parent_depth<depth{let mut l=self.nodes[h].pos;let mut r=self.nodes[v].pos;while l<r{let m=(l+r)>>1;let node_id=self.inv[m];if self.nodes[node_id].depth<depth{l=m+1;}else{r=m;}}return self.inv[l];}v=parent;}}}pub struct KthSubstrings<'a,T>where T:Ord{tree:&'a SuffixTree<T>,prefix_distinct:Vec<u64>,prefix_total:Vec<u64>}impl<'a,T>KthSubstrings<'a,T>where T:Ord{fn new(tree:&'a SuffixTree<T>)->Self{let n=tree.nodes.len();let mut prefix_distinct=vec![0u64;n];let mut prefix_total=vec![0u64;n];for i in 1..n{let node=&tree.nodes[i];let parent_depth=tree.nodes[node.parent].depth;let distinct=(node.depth-parent_depth)as u64;let total=distinct*node.sa_range.len()as u64;prefix_distinct[i]=prefix_distinct[i-1]+distinct;prefix_total[i]=prefix_total[i-1]+total;}Self{tree,prefix_distinct,prefix_total}}pub fn kth_distinct_substring(&self,k:u64)->Option<Range<usize>>{let idx=self.prefix_distinct.partition_point(|&x|x<=k);if idx==self.prefix_distinct.len(){return None;}let node=&self.tree.nodes[idx];let offset=k-self.prefix_distinct[idx-1];let len=self.tree.nodes[node.parent].depth+1+offset as usize;let start=self.tree.suffix_array[node.sa_range.start];Some(start..start+len)}pub fn kth_substring(&self,k:u64)->Option<Range<usize>>{let idx=self.prefix_total.partition_point(|&x|x<=k);if idx==self.prefix_total.len(){return None;}let node=&self.tree.nodes[idx];let offset=k-self.prefix_total[idx-1];let occ=node.sa_range.len()as u64;let len=self.tree.nodes[node.parent].depth+1+(offset/occ)as usize;let start=self.tree.suffix_array[node.sa_range.start+(offset%occ)as usize];Some(start..start+len)}pub fn index_of_distinct_substring(&self,range:Range<usize>)->u64{debug_assert!(range.start<range.end&&range.end<=self.tree.text.len());let m=range.len();let leaf=self.tree.leafs[self.tree.rank[range.start]];let node=self.tree.node_covering_depth(leaf,m);let offset=m-self.tree.nodes[self.tree.nodes[node].parent].depth-1;self.prefix_distinct[node-1]+offset as u64}pub fn index_of_substring(&self,range:Range<usize>)->u64{debug_assert!(range.start<range.end&&range.end<=self.tree.text.len());let m=range.len();let idx=self.tree.rank[range.start];let leaf=self.tree.leafs[idx];let node=self.tree.node_covering_depth(leaf,m);let offset=m-self.tree.nodes[self.tree.nodes[node].parent].depth-1;let occ=self.tree.nodes[node].sa_range.len()as u64;let occ_idx=(idx-self.tree.nodes[node].sa_range.start)as u64;self.prefix_total[node-1]+offset as u64*occ+occ_idx}}pub struct MultipleSuffixTree<T>where T:Ord+Clone{texts:Vec<Vec<T>>,offsets:Vec<usize>,tree:SuffixTree<Delimited<T>>,position_map:Vec<(usize,usize)>}impl<T>MultipleSuffixTree<T>where T:Ord+Clone{pub fn new(texts:Vec<Vec<T>>)->Self{assert!(!texts.is_empty());let total_len:usize=texts.iter().map(|text|text.len()+1).sum();let mut concat=Vec::with_capacity(total_len-1);let mut offsets=Vec::with_capacity(texts.len());let mut position_map=Vec::with_capacity(total_len);for(i,text)in texts.iter().enumerate(){offsets.push(concat.len());for(pos,value)in text.iter().cloned().enumerate(){concat.push(Delimited::Value(value));position_map.push((i,pos));}if i+1<texts.len(){concat.push(Delimited::Separator(!i));}position_map.push((i,text.len()));}let mut tree=SuffixTree::new(concat);for node_id in 0..tree.node_size(){if tree.children(node_id).is_empty(){let node=tree.node(node_id);let(text_idx,pos)=position_map[tree.suffix_array()[node.sa_range.start]];tree.nodes[node_id].depth=texts[text_idx].len()-pos;}}Self{texts,offsets,tree,position_map}}pub fn texts(&self)->&[Vec<T>]{&self.texts}pub fn suffix_array(&self)->&[usize]{self.tree.suffix_array()}pub fn lcp_array(&self)->&[usize]{self.tree.lcp_array()}pub fn rank(&self)->&[usize]{self.tree.rank()}pub fn node_size(&self)->usize{self.tree.node_size()}pub fn node(&self,node_id:usize)->&STNode{self.tree.node(node_id)}pub fn children(&self,node_id:usize)->&[usize]{self.tree.children(node_id)}pub fn position_map(&self)->&[(usize,usize)]{&self.position_map}pub fn depth_range(&self,node_id:usize)->Range<usize>{let node=self.tree.node(node_id);if node.parent==!0{return 0..0;}let parent_depth=self.tree.node(node.parent).depth;parent_depth+1..node.depth+1}pub fn kth_substrings(&self)->MultipleKthSubstrings<'_,T>{MultipleKthSubstrings::new(self)}fn to_global_start(&self,text_idx:usize,pos:usize)->usize{self.offsets[text_idx]+pos}}pub struct MultipleKthSubstrings<'a,T>where T:Ord+Clone{tree:&'a MultipleSuffixTree<T>,prefix_distinct:Vec<u64>,prefix_total:Vec<u64>}impl<'a,T>MultipleKthSubstrings<'a,T>where T:Ord+Clone{fn new(tree:&'a MultipleSuffixTree<T>)->Self{let n=tree.tree.nodes.len();let mut prefix_distinct=vec![0u64;n];let mut prefix_total=vec![0u64;n];for i in 1..n{let node=&tree.tree.nodes[i];let parent_depth=tree.tree.nodes[node.parent].depth;let distinct=(node.depth-parent_depth)as u64;let total=distinct*node.sa_range.len()as u64;prefix_distinct[i]=prefix_distinct[i-1]+distinct;prefix_total[i]=prefix_total[i-1]+total;}Self{tree,prefix_distinct,prefix_total}}pub fn kth_distinct_substring(&self,k:u64)->Option<(usize,Range<usize>)>{let idx=self.prefix_distinct.partition_point(|&x|x<=k);if idx==self.prefix_distinct.len(){return None;}let node=&self.tree.tree.nodes[idx];let parent_depth=self.tree.tree.nodes[node.parent].depth;let offset=k-self.prefix_distinct[idx-1];let len=parent_depth+1+offset as usize;let start=self.tree.tree.suffix_array[node.sa_range.start];let(text_idx,pos)=self.tree.position_map[start];Some((text_idx,pos..pos+len))}pub fn kth_substring(&self,k:u64)->Option<(usize,Range<usize>)>{let idx=self.prefix_total.partition_point(|&x|x<=k);if idx==self.prefix_total.len(){return None;}let node=&self.tree.tree.nodes[idx];let parent_depth=self.tree.tree.nodes[node.parent].depth;let offset=k-self.prefix_total[idx-1];let occ=node.sa_range.len()as u64;let len_offset=(offset/occ)as usize;let occ_idx=(offset%occ)as usize;let len=parent_depth+1+len_offset;let start=self.tree.tree.suffix_array[node.sa_range.start+occ_idx];let(text_idx,pos)=self.tree.position_map[start];Some((text_idx,pos..pos+len))}pub fn index_of_distinct_substring(&self,(text_idx,range):(usize,Range<usize>))->u64{debug_assert!(text_idx<self.tree.texts.len());debug_assert!(range.start<range.end&&range.end<=self.tree.texts[text_idx].len());let m=range.len();let start=self.tree.to_global_start(text_idx,range.start);let sa_idx=self.tree.tree.rank[start];let leaf=self.tree.tree.leafs[sa_idx];let node=self.tree.tree.node_covering_depth(leaf,m);let parent_depth=self.tree.tree.nodes[self.tree.tree.nodes[node].parent].depth;let offset=m-(parent_depth+1);self.prefix_distinct[node-1]+offset as u64}pub fn index_of_substring(&self,(text_idx,range):(usize,Range<usize>))->u64{debug_assert!(text_idx<self.tree.texts.len());debug_assert!(range.start<range.end&&range.end<=self.tree.texts[text_idx].len());let m=range.len();let start=self.tree.to_global_start(text_idx,range.start);let sa_idx=self.tree.tree.rank[start];let leaf=self.tree.tree.leafs[sa_idx];let node=self.tree.tree.node_covering_depth(leaf,m);let parent_depth=self.tree.tree.nodes[self.tree.tree.nodes[node].parent].depth;let offset=m-(parent_depth+1);let occ=self.tree.tree.nodes[node].sa_range.len()as u64;let occ_idx=(sa_idx-self.tree.tree.nodes[node].sa_range.start)as u64;self.prefix_total[node-1]+offset as u64*occ+occ_idx}}}
// 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}}