// codesnip-guard: RangeFoldWithUpperBound
#[cfg_attr(any(),rustfmt::skip)]pub use self::range_fold_with_upper_bound::RangeFoldWithUpperBound;#[cfg_attr(any(),rustfmt::skip)]mod range_fold_with_upper_bound{use super::{AbelianGroup,BinaryIndexedTree,RadixSortKey,SliceSortExt};use std::ops::Range;#[doc=" Offline range folds over entries whose keys are at most a query bound."]pub struct RangeFoldWithUpperBound<K,M>where M:AbelianGroup{keys:Vec<K>,weights:Vec<M::T>,queries:Vec<(Range<usize>,K)>}impl<K,M>RangeFoldWithUpperBound<K,M>where K:RadixSortKey+Ord,M:AbelianGroup{pub fn new(values:impl IntoIterator<Item=(K,M::T)>)->Self{let(keys,weights)=values.into_iter().unzip();Self{keys,weights,queries:Vec::new()}}pub fn query(&mut self,range:Range<usize>,upper_bound:K)->usize{let index=self.queries.len();self.queries.push((range,upper_bound));index}pub fn execute(self)->Vec<M::T>{let mut values:Vec<_>=self.keys.iter().copied().enumerate().map(|(index,key)|(key,index)).collect();values.radix_sort_by_key(|&(key,_)|key);let mut order:Vec<_>=self.queries.iter().enumerate().map(|(index,(_,upper_bound))|(*upper_bound,index)).collect();order.radix_sort_by_key(|&(upper_bound,_)|upper_bound);let mut bit:BinaryIndexedTree<M>=BinaryIndexedTree::new(values.len());let mut answers=vec![M::unit();self.queries.len()];let mut inserted=0;for(upper_bound,index)in order{while inserted<values.len()&&values[inserted].0<=upper_bound{let position=values[inserted].1;bit.update(position,self.weights[position].clone());inserted+=1;}let range=&self.queries[index].0;answers[index]=bit.fold(range.start,range.end);}answers}}}
// codesnip-guard: BinaryIndexedTree
#[cfg_attr(any(),rustfmt::skip)]pub use self::binary_indexed_tree::BinaryIndexedTree;#[cfg_attr(any(),rustfmt::skip)]mod binary_indexed_tree{use super::{AbelianGroup,Group,Monoid};use std::fmt::{self,Debug,Formatter};pub struct BinaryIndexedTree<M>where M:Monoid{n:usize,bit:Vec<M::T>}impl<M>Clone for BinaryIndexedTree<M>where M:Monoid{fn clone(&self)->Self{Self{n:self.n,bit:self.bit.clone()}}}impl<M>Debug for BinaryIndexedTree<M>where M:Monoid<T:Debug>{fn fmt(&self,f:&mut Formatter<'_>)->fmt::Result{f.debug_struct("BinaryIndexedTree").field("n",&self.n).field("bit",&self.bit).finish()}}impl<M>BinaryIndexedTree<M>where M:Monoid{#[inline]pub fn new(n:usize)->Self{let bit=vec![M::unit();n+1];Self{n,bit}}#[inline]pub fn from_slice(slice:&[M::T])->Self{let n=slice.len();let mut bit=vec![M::unit();n+1];for(i,x)in slice.iter().enumerate(){let k=i+1;M::operate_assign(&mut bit[k],x);let j=k+(k&(!k+1));if j<=n{bit[j]=M::operate(&bit[j],&bit[k]);}}Self{n,bit}}#[inline]#[doc=" fold [0, k)"]pub fn accumulate0(&self,mut k:usize)->M::T{debug_assert!(k<=self.n);let mut res=M::unit();while k>0{res=M::operate(&self.bit[k],&res);k-=k&(!k+1);}res}#[inline]#[doc=" fold [0, k]"]pub fn accumulate(&self,k:usize)->M::T{self.accumulate0(k+1)}#[inline]pub fn update(&mut self,k:usize,x:M::T){debug_assert!(k<self.n);let mut k=k+1;while k<=self.n{self.bit[k]=M::operate(&self.bit[k],&x);k+=k&(!k+1);}}#[inline]pub fn partition_point_acc<P>(&self,mut pred:P)->usize where P:FnMut(&M::T)->bool{let n=self.n;let mut acc=M::unit();let mut pos=0;let mut k=n.next_power_of_two();while k>0{if k+pos<=n{let nacc=M::operate(&acc,&self.bit[k+pos]);if pred(&nacc){pos+=k;acc=nacc;}}k>>=1;}pos}}impl<G:Group>BinaryIndexedTree<G>{#[inline]pub fn fold(&self,l:usize,r:usize)->G::T{debug_assert!(l<=self.n&&r<=self.n);G::operate(&G::inverse(&self.accumulate0(l)),&self.accumulate0(r))}#[inline]pub fn fold_abelian(&self,mut l:usize,mut r:usize)->G::T where G:AbelianGroup{debug_assert!(l<=self.n&&r<=self.n);if l==r{return G::unit();}let common=l&!(usize::MAX>>(l^r).leading_zeros());let mut left=G::unit();let mut right=G::unit();while l!=common{G::operate_assign(&mut left,&self.bit[l]);l&=l-1;}while r!=common{G::operate_assign(&mut right,&self.bit[r]);r&=r-1;}G::rinv_operate(&right,&left)}#[inline]pub fn get(&self,k:usize)->G::T{self.fold(k,k+1)}#[inline]pub fn set(&mut self,k:usize,x:G::T){self.update(k,G::operate(&G::inverse(&self.get(k)),&x));}}}
// codesnip-guard: algebra
#[cfg_attr(any(),rustfmt::skip)]pub use self::magma::*;#[cfg_attr(any(),rustfmt::skip)]mod magma{#![doc=" algebraic traits"]#[doc=" binary operaion: $T \\circ T \\to T$"]pub trait Magma{#[doc=" type of operands: $T$"]type T:Clone;#[doc=" binary operaion: $\\circ$"]fn operate(x:&Self::T,y:&Self::T)->Self::T;fn reverse_operate(x:&Self::T,y:&Self::T)->Self::T{Self::operate(y,x)}fn operate_assign(x:&mut Self::T,y:&Self::T){*x=Self::operate(x,y);}}#[doc=" $\\forall a,\\forall b,\\forall c \\in T, (a \\circ b) \\circ c = a \\circ (b \\circ c)$"]pub trait Associative:Magma{}#[doc=" associative binary operation"]pub trait SemiGroup:Magma+Associative{}impl<S>SemiGroup for S where S:Magma+Associative{}#[doc=" $\\exists e \\in T, \\forall a \\in T, e \\circ a = a \\circ e = a$"]pub trait Unital:Magma{#[doc=" identity element: $e$"]fn unit()->Self::T;fn is_unit(x:&Self::T)->bool where Self::T:PartialEq{x==&Self::unit()}fn set_unit(x:&mut Self::T){*x=Self::unit();}}pub trait ExpBits{type Iter:Iterator<Item=bool>;fn bits(self)->Self::Iter;}pub trait SignedExpBits{type T:ExpBits;fn neg_and_bits(self)->(bool,Self::T);}pub struct Bits<T>{n:T}macro_rules!impl_exp_bits_for_uint{($($t:ty)*)=>{$(impl Iterator for Bits<$t>{type Item=bool;fn next(&mut self)->Option<bool>{if self.n==0{None}else{let bit=(self.n&1)==1;self.n>>=1;Some(bit)}}}impl ExpBits for$t{type Iter=Bits<$t>;fn bits(self)->Self::Iter{Bits{n:self}}}impl SignedExpBits for$t{type T=$t;fn neg_and_bits(self)->(bool,Self::T){(false,self)}})*};}impl_exp_bits_for_uint!(u8 u16 u32 u64 u128 usize);macro_rules!impl_signed_exp_bits_for_sint{($($s:ty,$u:ty;)*)=>{$(impl SignedExpBits for$s{type T=$u;fn neg_and_bits(self)->(bool,Self::T){(self<0,self.unsigned_abs())}})*};}impl_signed_exp_bits_for_sint!(i8,u8;i16,u16;i32,u32;i64,u64;i128,u128;isize,usize;);#[doc=" associative binary operation and an identity element"]pub trait Monoid:SemiGroup+Unital{#[doc=" binary exponentiation: $x^n = x\\circ\\ddots\\circ x$"]fn pow<E>(mut x:Self::T,exp:E)->Self::T where E:ExpBits{let mut bits=exp.bits();let Some(first)=bits.next()else{return Self::unit();};let mut res=if first{x.clone()}else{Self::unit()};for bit in bits{x=Self::operate(&x,&x);if bit{res=Self::operate(&res,&x);}}res}fn fold<I>(iter:I)->Self::T where I:IntoIterator<Item=Self::T>{let mut iter=iter.into_iter();if let Some(item)=iter.next(){iter.fold(item,|acc,x|Self::operate(&acc,&x))}else{Self::unit()}}}impl<M>Monoid for M where M:SemiGroup+Unital{}#[doc=" $\\exists e \\in T, \\forall a \\in T, \\exists b,c \\in T, b \\circ a = a \\circ c = e$"]pub trait Invertible:Magma+Unital{#[doc=" $a$ where $a \\circ x = e$"]fn inverse(x:&Self::T)->Self::T;fn rinv_operate(x:&Self::T,y:&Self::T)->Self::T{Self::operate(x,&Self::inverse(y))}fn rinv_operate_assign(x:&mut Self::T,y:&Self::T){*x=Self::rinv_operate(x,y);}}#[doc=" associative binary operation and an identity element and inverse elements"]pub trait Group:Monoid+Invertible{fn signed_pow<E>(x:Self::T,exp:E)->Self::T where E:SignedExpBits{let(neg,exp)=E::neg_and_bits(exp);let res=Self::pow(x,exp);if neg{Self::inverse(&res)}else{res}}}impl<G>Group for G where G:Monoid+Invertible{}#[doc=" $\\forall a,\\forall b \\in T, a \\circ b = b \\circ a$"]pub trait Commutative:Magma{}#[doc=" commutative monoid"]pub trait AbelianMonoid:Monoid+Commutative{}impl<M>AbelianMonoid for M where M:Monoid+Commutative{}#[doc=" commutative group"]pub trait AbelianGroup:Group+Commutative{}impl<G>AbelianGroup for G where G:Group+Commutative{}#[doc=" $\\forall a \\in T, a \\circ a = a$"]pub trait Idempotent:Magma{}#[doc=" idempotent monoid"]pub trait IdempotentMonoid:Monoid+Idempotent{}impl<M>IdempotentMonoid for M where M:Monoid+Idempotent{}#[macro_export]macro_rules!monoid_fold{($m:ty)=>{<$m as Unital>::unit()};($m:ty,)=>{<$m as Unital>::unit()};($m:ty,$f:expr)=>{$f};($m:ty,$f:expr,$($ff:expr),*)=>{<$m as Magma>::operate(&($f),&monoid_fold!($m,$($ff),*))};}#[macro_export]macro_rules!define_monoid{($Name:ident,$t:ty,|$x:ident,$y:ident|$op:expr,$unit:expr)=>{struct$Name;impl Magma for$Name{type T=$t;fn operate($x:&Self::T,$y:&Self::T)->Self::T{$op}}impl Unital for$Name{fn unit()->Self::T{$unit}}impl Associative for$Name{}};}}
// codesnip-guard: sort
#[cfg_attr(any(),rustfmt::skip)]pub use self::sort::{RadixSortKey,SliceSortExt};#[cfg_attr(any(),rustfmt::skip)]mod sort{use std::{cmp::Ordering,ptr::copy_nonoverlapping};pub trait RadixSortKey:Copy{const BYTES:usize;fn radix_byte(self,byte:usize)->usize;}macro_rules!unsigned_radix_sort_key{($($t:ty),*$(,)?)=>{$(impl RadixSortKey for$t{const BYTES:usize=(<$t>::BITS/8)as usize;fn radix_byte(self,byte:usize)->usize{((self>>(byte*8))&0xff)as usize}})*};}macro_rules!signed_radix_sort_key{($($t:ty=>$u:ty),*$(,)?)=>{$(impl RadixSortKey for$t{const BYTES:usize=(<$t>::BITS/8)as usize;fn radix_byte(self,byte:usize)->usize{let key=self as$u^(1<<(<$t>::BITS-1));((key>>(byte*8))&0xff)as usize}})*};}unsigned_radix_sort_key!(u8,u16,u32,u64,u128,usize);signed_radix_sort_key!(i8=>u8,i16=>u16,i32=>u32,i64=>u64,i128=>u128,isize=>usize,);pub trait SliceSortExt<T>{fn bubble_sort(&mut self)where T:Ord;fn bubble_sort_by<F>(&mut self,compare:F)where F:FnMut(&T,&T)->Ordering;fn merge_sort(&mut self)where T:Ord;fn merge_sort_by<F>(&mut self,compare:F)where F:FnMut(&T,&T)->Ordering;fn insertion_sort(&mut self)where T:Ord;fn insertion_sort_by<F>(&mut self,compare:F)where F:FnMut(&T,&T)->Ordering;fn radix_sort_by_key<K>(&mut self,key:impl FnMut(&T)->K)where T:Clone,K:RadixSortKey;}impl<T>SliceSortExt<T>for[T]{fn bubble_sort(&mut self)where T:Ord{bubble_sort(self,|a,b|a.lt(b));}fn bubble_sort_by<F>(&mut self,mut compare:F)where F:FnMut(&T,&T)->Ordering{bubble_sort(self,|a,b|compare(a,b)==Ordering::Less);}fn merge_sort(&mut self)where T:Ord{merge_sort(self,|a,b|a.lt(b));}fn merge_sort_by<F>(&mut self,mut compare:F)where F:FnMut(&T,&T)->Ordering{merge_sort(self,|a,b|compare(a,b)==Ordering::Less);}fn insertion_sort(&mut self)where T:Ord{insertion_sort(self,|a,b|a.lt(b));}fn insertion_sort_by<F>(&mut self,mut compare:F)where F:FnMut(&T,&T)->Ordering{insertion_sort(self,|a,b|compare(a,b)==Ordering::Less);}fn radix_sort_by_key<K>(&mut self,key:impl FnMut(&T)->K)where T:Clone,K:RadixSortKey{radix_sort_by_key(self,key);}}fn radix_sort_by_key<T,K>(values:&mut[T],mut key:impl FnMut(&T)->K)where T:Clone,K:RadixSortKey{if values.len()<=1{return;}let mut histograms=vec![[0usize;256];K::BYTES];for value in values.iter(){let key=key(value);for(byte,histogram)in histograms.iter_mut().enumerate(){histogram[key.radix_byte(byte)]+=1;}}for histogram in histograms.iter_mut(){let mut position=0;for count in histogram.iter_mut(){let next=position+*count;*count=position;position=next;}}let mut ends=[values.len();256];ends[..255].copy_from_slice(&histograms[0][1..]);let mut buffer=Vec::with_capacity(values.len());{let spare=buffer.spare_capacity_mut();let positions=&mut histograms[0];for value in values.iter(){let bucket=key(value).radix_byte(0);let position=&mut positions[bucket];assert!(*position<ends[bucket]);spare[*position].write(value.clone());*position+=1;}}unsafe{buffer.set_len(values.len())};for(byte,positions)in histograms.iter_mut().enumerate().skip(1){macro_rules!distribute{($source:expr,$destination:expr)=>{{let source=$source;let destination=$destination;for value in source{let bucket=key(value).radix_byte(byte);let position=&mut positions[bucket];destination[*position].clone_from(value);*position+=1;}}};}if byte%2==0{distribute!(&*values,&mut buffer);}else{distribute!(&buffer,&mut*values);}}if K::BYTES%2==1{values.clone_from_slice(&buffer);}}fn bubble_sort<T,F>(v:&mut[T],mut is_less:F)where F:FnMut(&T,&T)->bool{let len=v.len();if len<=1{return;}for i in 0..len-1{for j in 0..len-i-1{unsafe{if is_less(v.get_unchecked(j+1),v.get_unchecked(j)){v.swap(j,j+1);}}}}}unsafe fn merge<T,F>(v:&mut[T],mid:usize,buf:*mut T,is_less:&mut F)where F:FnMut(&T,&T)->bool{unsafe{let len=v.len();let v=v.as_mut_ptr();let(v_mid,v_end)=(v.add(mid),v.add(len));copy_nonoverlapping(v,buf,mid);let mut guard=MergeGuard{start:buf,dest:v,len:mid};let mut right=v_mid;while guard.len!=0&&right<v_end{let to_copy=if is_less(&*right,&*guard.start){get_and_increment(&mut right)}else{guard.len-=1;get_and_increment(&mut guard.start)};copy_nonoverlapping(to_copy,get_and_increment(&mut guard.dest),1);}}struct MergeGuard<T>{start:*mut T,dest:*mut T,len:usize}impl<T>Drop for MergeGuard<T>{fn drop(&mut self){unsafe{copy_nonoverlapping(self.start,self.dest,self.len)};}}unsafe fn get_and_increment<T>(ptr:&mut*mut T)->*mut T{let old=*ptr;*ptr=unsafe{ptr.offset(1)};old}}fn merge_sort<T,F>(v:&mut[T],mut is_less:F)where F:FnMut(&T,&T)->bool{let len=v.len();if len<=1{return;}let mut buf=Vec::with_capacity(len/2);let mut runs:Vec<Run>=vec![];let mut end=len;while end>0{let start=end-1;let mut left=Run{start,len:end-start};end=start;while let Some(right)=runs.pop_if(|right|left.start==0||right.len<=left.len){unsafe{merge(&mut v[left.start..right.start+right.len],left.len,buf.as_mut_ptr(),&mut is_less);}left=Run{start:left.start,len:left.len+right.len};}runs.push(left);}debug_assert!(runs.len()==1&&runs[0].start==0&&runs[0].len==len);#[derive(Clone,Copy)]struct Run{start:usize,len:usize}}fn insertion_sort<T,F>(v:&mut[T],mut is_less:F)where F:FnMut(&T,&T)->bool{for i in 1..v.len(){let x=&v[i];let p=v[..i].partition_point(|y|is_less(y,x));v[p..=i].rotate_right(1);}}}