// codesnip-guard: CompressedSegmentTree
#[cfg_attr(any(),rustfmt::skip)]pub use self::compressed_segment_tree::{CompressedSegmentTree,CompressedSegmentTree1d,CompressedSegmentTree2d,CompressedSegmentTree3d,CompressedSegmentTree4d};#[cfg_attr(any(),rustfmt::skip)]mod compressed_segment_tree{use super::Monoid;use std::{fmt::{self,Debug},marker::PhantomData,ops::{Bound,RangeBounds}};pub struct CompressedSegmentTree<M,X,Inner>where M:Monoid{compress:Vec<X>,segs:Vec<Inner>,_marker:PhantomData<fn()->M>}impl<M,X,Inner>Debug for CompressedSegmentTree<M,X,Inner>where M:Monoid,X:Debug,Inner:Debug{fn fmt(&self,f:&mut fmt::Formatter<'_>)->fmt::Result{f.debug_struct("CompressedSegmentTree").field("compress",&self.compress).field("segs",&self.segs).finish()}}impl<M,X,Inner>Clone for CompressedSegmentTree<M,X,Inner>where M:Monoid,X:Clone,Inner:Clone{fn clone(&self)->Self{Self{compress:self.compress.clone(),segs:self.segs.clone(),_marker:self._marker}}}impl<M,X,Inner>Default for CompressedSegmentTree<M,X,Inner>where M:Monoid{fn default()->Self{Self{compress:Default::default(),segs:Default::default(),_marker:Default::default()}}}#[repr(transparent)]pub struct Tag<M>(M::T)where M:Monoid;impl<M>Debug for Tag<M>where M:Monoid<T:Debug>{fn fmt(&self,f:&mut fmt::Formatter<'_>)->fmt::Result{self.0 .fmt(f)}}impl<M>Clone for Tag<M>where M:Monoid{fn clone(&self)->Self{Self(self.0 .clone())}}impl<M,X>CompressedSegmentTree<M,X,Tag<M>>where M:Monoid,X:Clone+Ord{fn merge_1d_coordinates(left:&Self,right:&Self)->Self{let left=&left.compress;let right=&right.compress;let mut compress=Vec::with_capacity(left.len()+right.len());let mut l=0;let mut r=0;while l<left.len()&&r<right.len(){match left[l].cmp(&right[r]){std::cmp::Ordering::Less=>{compress.push(left[l].clone());l+=1;}std::cmp::Ordering::Equal=>{compress.push(left[l].clone());l+=1;r+=1;}std::cmp::Ordering::Greater=>{compress.push(right[r].clone());r+=1;}}}compress.extend_from_slice(&left[l..]);compress.extend_from_slice(&right[r..]);let n=compress.len();Self{compress,segs:vec![Tag(M::unit());n*2],_marker:PhantomData}}}trait MergeCoordinates<M>:Clone where M:Monoid{fn empty()->Self;fn merge_coordinates(left:&Self,right:&Self)->Self;}impl<M>MergeCoordinates<M>for Tag<M>where M:Monoid{fn empty()->Self{Self(M::unit())}fn merge_coordinates(_:&Self,_:&Self)->Self{Self::empty()}}impl<M,X,Inner>MergeCoordinates<M>for CompressedSegmentTree<M,X,Inner>where M:Monoid,X:Clone+Ord,Inner:MergeCoordinates<M>{fn empty()->Self{Self::default()}fn merge_coordinates(left:&Self,right:&Self)->Self{let left_values=&left.compress;let right_values=&right.compress;let mut compress=Vec::with_capacity(left_values.len()+right_values.len());let mut leaves=Vec::with_capacity(compress.capacity());let mut l=0;let mut r=0;while l<left_values.len()&&r<right_values.len(){match left_values[l].cmp(&right_values[r]){std::cmp::Ordering::Less=>{compress.push(left_values[l].clone());leaves.push(left.segs[left_values.len()+l].clone());l+=1;}std::cmp::Ordering::Equal=>{compress.push(left_values[l].clone());leaves.push(Inner::merge_coordinates(&left.segs[left_values.len()+l],&right.segs[right_values.len()+r]));l+=1;r+=1;}std::cmp::Ordering::Greater=>{compress.push(right_values[r].clone());leaves.push(right.segs[right_values.len()+r].clone());r+=1;}}}for(coordinate,leaf)in left_values[l..].iter().zip(&left.segs[left_values.len()+l..]){compress.push(coordinate.clone());leaves.push(leaf.clone());}for(coordinate,leaf)in right_values[r..].iter().zip(&right.segs[right_values.len()+r..]){compress.push(coordinate.clone());leaves.push(leaf.clone());}let n=compress.len();let mut segs=vec![Inner::empty();n];segs.extend(leaves);for i in(1..n).rev(){segs[i]=Inner::merge_coordinates(&segs[i*2],&segs[i*2+1]);}Self{compress,segs,_marker:PhantomData}}}macro_rules!impl_compressed_segment_tree{(@tuple($($l:tt)*)($($r:tt)*)$T:ident)=>{($($l)*$T$($r)*,)};(@tuple($($l:tt)*)($($r:tt)*)$T:ident$($Rest:ident)+)=>{($($l)*$T$($r)*,impl_compressed_segment_tree!(@tuple($($l)*)($($r)*)$($Rest)+))};(@cst$M:ident)=>{Tag<$M>};(@cst$M:ident$T:ident$($Rest:ident)*)=>{CompressedSegmentTree<$M,$T,impl_compressed_segment_tree!(@cst$M$($Rest)*)>};(@from_iter$M:ident$points:ident$T:ident)=>{{let mut compress:Vec<_> =$points.into_iter().map(|t|t.0 .clone()).collect();compress.sort_unstable();compress.dedup();let n=compress.len();Self{compress,segs:vec![Tag(M::unit());n*2],_marker:PhantomData,}}};(@from_iter$M:ident$points:ident$T:ident$U:ident)=>{{let mut points:Vec<_> =$points.into_iter().collect();points.sort_unstable_by(|left,right|left.0 .cmp(&right.0));let mut compress=Vec::new();let mut offsets=vec![0];let mut start=0;while start<points.len(){let mut end=start+1;while end<points.len()&&points[end].0==points[start].0{end+=1;}compress.push(points[start].0 .clone());offsets.push(end);start=end;}let n=compress.len();let mut segs:Vec<impl_compressed_segment_tree!(@cst$M$U)> =vec![Default::default();n];for i in 0..n{segs.push(<impl_compressed_segment_tree!(@cst$M$U)>::from_iter(points[offsets[i]..offsets[i+1]].iter().map(|point|&point.1),));}for i in(1..n).rev(){segs[i]=CompressedSegmentTree::merge_1d_coordinates(&segs[i*2],&segs[i*2+1],);}Self{compress,segs,_marker:PhantomData,}}};(@from_iter$M:ident$points:ident$T:ident$U:ident$($Rest:ident)*)=>{{let mut points:Vec<_> =$points.into_iter().collect();points.sort_unstable_by(|left,right|left.0 .cmp(&right.0));let mut compress=Vec::new();let mut offsets=vec![0];let mut start=0;while start<points.len(){let mut end=start+1;while end<points.len()&&points[end].0==points[start].0{end+=1;}compress.push(points[start].0 .clone());offsets.push(end);start=end;}let n=compress.len();let mut segs:Vec<impl_compressed_segment_tree!(@cst$M$U$($Rest)*)> =vec![Default::default();n];for i in 0..n{segs.push(<impl_compressed_segment_tree!(@cst$M$U$($Rest)*)>::from_iter(points[offsets[i]..offsets[i+1]].iter().map(|point|&point.1),));}for i in(1..n).rev(){segs[i]=MergeCoordinates::merge_coordinates(&segs[i*2],&segs[i*2+1]);}Self{compress,segs,_marker:PhantomData,}}};(@fold$e:expr,$rng:ident$T:ident)=>{$e.0};(@fold$e:expr,$rng:ident$T:ident$($Rest:ident)+)=>{$e.fold(&$rng.1)};(@update$e:expr,$M:ident$key:ident$x:ident$T:ident)=>{$M::operate_assign(&mut$e.0,$x);};(@update$e:expr,$M:ident$key:ident$x:ident$T:ident$($Rest:ident)+)=>{$e.update(&$key.1,$x);};(@partition_value$e:expr)=>{$e.0};(@partition_value$e:expr,$inner_ranges:ident)=>{$e.fold($inner_ranges)};(@partition_perfect_body$this:tt,$pos:expr,$acc:expr,$pred:ident$(,$inner_ranges:ident)?)=>{{let n=$this.compress.len();let mut pos=$pos;let mut acc=$acc;while pos<n{pos<<=1;let nacc=M::operate(&acc,&impl_compressed_segment_tree!(@partition_value$this.segs[pos]$(,$inner_ranges)?),);if$pred(&nacc){acc=nacc;pos+=1;}}(pos-n,acc)}};(@rpartition_perfect_body$this:tt,$pos:expr,$acc:expr,$pred:ident$(,$inner_ranges:ident)?)=>{{let n=$this.compress.len();let mut pos=$pos;let mut acc=$acc;while pos<n{pos=pos*2+1;let nacc=M::operate(&impl_compressed_segment_tree!(@partition_value$this.segs[pos]$(,$inner_ranges)?),&acc,);if$pred(&nacc){acc=nacc;pos-=1;}}(pos-n+1,acc)}};(@partition_body$this:tt,$left:ident,$pred:ident$(,$inner_ranges:ident)?)=>{{let n=$this.compress.len();let mut l=$this.compress.partition_point(|x|x<$left)+n;let r=2*n;let mut k=0usize;let mut acc=M::unit();while l<r>>k{if l&1!=0{let nacc=M::operate(&acc,&impl_compressed_segment_tree!(@partition_value$this.segs[l]$(,$inner_ranges)?),);if!$pred(&nacc){let(pos,acc)=impl_compressed_segment_tree!(@partition_perfect_body$this,l,acc,$pred$(,$inner_ranges)?);return($this.compress.get(pos),acc);}acc=nacc;l+=1;}l>>=1;k+=1;}for k in(0..k).rev(){let r=r>>k;if r&1!=0{let nacc=M::operate(&acc,&impl_compressed_segment_tree!(@partition_value$this.segs[r-1]$(,$inner_ranges)?),);if!$pred(&nacc){let(pos,acc)=impl_compressed_segment_tree!(@partition_perfect_body$this,r-1,acc,$pred$(,$inner_ranges)?);return($this.compress.get(pos),acc);}acc=nacc;}}($this.compress.get(n),acc)}};(@rpartition_body$this:tt,$right:ident,$pred:ident$(,$inner_ranges:ident)?)=>{{let n=$this.compress.len();let mut l=n;let mut r=$this.compress.partition_point(|x|x<$right)+n;let mut c=0usize;let mut k=0usize;let mut acc=M::unit();while l>>k<r{c<<=1;if l&(1<<k)!=0{l+=1<<k;c+=1;}if r&1!=0{r-=1;let nacc=M::operate(&impl_compressed_segment_tree!(@partition_value$this.segs[r]$(,$inner_ranges)?),&acc,);if!$pred(&nacc){let(pos,acc)=impl_compressed_segment_tree!(@rpartition_perfect_body$this,r,acc,$pred$(,$inner_ranges)?);return($this.compress.get(pos),acc);}acc=nacc;}r>>=1;k+=1;}for k in(0..k).rev(){if c&1!=0{l-=1<<k;let l=l>>k;let nacc=M::operate(&impl_compressed_segment_tree!(@partition_value$this.segs[l]$(,$inner_ranges)?),&acc,);if!$pred(&nacc){let(pos,acc)=impl_compressed_segment_tree!(@rpartition_perfect_body$this,l,acc,$pred$(,$inner_ranges)?);return($this.compress.get(pos),acc);}acc=nacc;}c>>=1;}($this.compress.first(),acc)}};(@partition_methods$T:ident,$Q:ident)=>{pub fn partition_point_acc<P>(&self,left:&$T,mut pred:P,)->(Option<&$T>,M::T)where P:FnMut(&M::T)->bool,{impl_compressed_segment_tree!(@partition_body self,left,pred)}pub fn rpartition_point_acc<P>(&self,right:&$T,mut pred:P,)->(Option<&$T>,M::T)where P:FnMut(&M::T)->bool,{impl_compressed_segment_tree!(@rpartition_body self,right,pred)}};(@partition_methods$T:ident$($RestT:ident)+,$Q:ident$($RestQ:ident)+)=>{pub fn partition_point_acc<P,$($RestQ,)*>(&self,left:&$T,inner_ranges:&impl_compressed_segment_tree!(@tuple()()$($RestQ)*),mut pred:P,)->(Option<&$T>,M::T)where P:FnMut(&M::T)->bool,$($RestQ:RangeBounds<$RestT>,)*{impl_compressed_segment_tree!(@partition_body self,left,pred,inner_ranges)}pub fn rpartition_point_acc<P,$($RestQ,)*>(&self,right:&$T,inner_ranges:&impl_compressed_segment_tree!(@tuple()()$($RestQ)*),mut pred:P,)->(Option<&$T>,M::T)where P:FnMut(&M::T)->bool,$($RestQ:RangeBounds<$RestT>,)*{impl_compressed_segment_tree!(@rpartition_body self,right,pred,inner_ranges)}};(@impl$C:ident$($T:ident)*,$($Q:ident)*)=>{impl<M,$($T,)*>impl_compressed_segment_tree!(@cst M$($T)*)where M:Monoid,$($T:Clone+Ord,)*{pub fn new(points:&[impl_compressed_segment_tree!(@tuple()()$($T)*)])->Self{Self::from_iter(points)}fn from_iter<'a,Iter>(points:Iter)->Self where$($T:'a,)*Iter:IntoIterator<Item=&'a impl_compressed_segment_tree!(@tuple()()$($T)*)>+Clone,{impl_compressed_segment_tree!(@from_iter M points$($T)*)}pub fn fold<$($Q,)*>(&self,range:&impl_compressed_segment_tree!(@tuple()()$($Q)*))->M::T where$($Q:RangeBounds<$T>,)*{let mut l=match range.0 .start_bound(){Bound::Included(index)=>self.compress.partition_point(|x|x<index),Bound::Excluded(index)=>self.compress.partition_point(|x|x<=index),Bound::Unbounded=>0,}+self.compress.len();let mut r=match range.0 .end_bound(){Bound::Included(index)=>self.compress.partition_point(|x|x<=index),Bound::Excluded(index)=>self.compress.partition_point(|x|x<index),Bound::Unbounded=>self.compress.len(),}+self.compress.len();let mut x=M::unit();while l<r{if l&1!=0{x=M::operate(&x,&impl_compressed_segment_tree!(@fold self.segs[l],range$($T)*));l+=1;}if r&1!=0{r-=1;x=M::operate(&impl_compressed_segment_tree!(@fold self.segs[r],range$($T)*),&x);}l/=2;r/=2;}x}pub fn update(&mut self,key:&impl_compressed_segment_tree!(@tuple()()$($T)*),x:&M::T){let mut i=self.compress.binary_search(&key.0).expect("not exist key")+self.compress.len();while i>0{impl_compressed_segment_tree!(@update self.segs[i],M key x$($T)*);i/=2;}}impl_compressed_segment_tree!(@partition_methods$($T)*,$($Q)*);}pub type$C<M,$($T),*> =impl_compressed_segment_tree!(@cst M$($T)*);};(@inner[$C:ident][$($T:ident)*][$($Q:ident)*][])=>{impl_compressed_segment_tree!(@impl$C$($T)*,$($Q)*);};(@inner[$C:ident][$($T:ident)*][$($Q:ident)*][$D:ident$U:ident$R:ident$($Rest:ident)*])=>{impl_compressed_segment_tree!(@impl$C$($T)*,$($Q)*);impl_compressed_segment_tree!(@inner[$D][$($T)*$U][$($Q)*$R][$($Rest)*]);};($C:ident$T:ident$Q:ident$($Rest:ident)*$(;$($t:tt)*)?)=>{impl_compressed_segment_tree!(@inner[$C][$T][$Q][$($Rest)*]);};}impl_compressed_segment_tree!(CompressedSegmentTree1d T1 Q1 CompressedSegmentTree2d T2 Q2 CompressedSegmentTree3d T3 Q3 CompressedSegmentTree4d T4 Q4;CompressedSegmentTree5d T5 Q5 CompressedSegmentTree6d T6 Q6 CompressedSegmentTree7d T7 Q7 CompressedSegmentTree8d T8 Q8 CompressedSegmentTree9d T9 Q9);}
// 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{}};}}