// codesnip-guard: StaticRangeProduct
#[cfg_attr(any(),rustfmt::skip)]pub use self::static_range_product::StaticRangeProduct;#[cfg_attr(any(),rustfmt::skip)]mod static_range_product{use super::{DisjointSparseTable,SemiGroup};use std::fmt::{self,Debug,Formatter};const DIRECT_SIZE:usize=4;const BLOCK_SCALE:usize=4;struct BlockProducts<T>{prefix:Vec<T>,suffix:Vec<T>,products:Vec<T>}#[derive(Clone)]pub struct StaticRangeProduct<S>where S:SemiGroup{data:Vec<S::T>,block_shift:usize,prefix:Vec<S::T>,suffix:Vec<S::T>,between:Option<FixedRangeProduct<S>>}impl<S>Debug for StaticRangeProduct<S>where S:SemiGroup<T:Debug>{fn fmt(&self,f:&mut Formatter<'_>)->fmt::Result{f.debug_struct("StaticRangeProduct").field("data",&self.data).field("block_size",&(1usize<<self.block_shift)).field("prefix",&self.prefix).field("suffix",&self.suffix).field("between",&self.between).finish()}}impl<S>StaticRangeProduct<S>where S:SemiGroup{pub fn new(data:Vec<S::T>)->Self{let n=data.len();if n==0{return Self{data,block_shift:0,prefix:Vec::new(),suffix:Vec::new(),between:None};}let block_shift=scaled_block_shift(inverse_ackermann(n));let block_size=1usize<<block_shift;let blocks=block_products::<S>(&data,block_size);let between=if blocks.products.len()>2{let level=inverse_ackermann(blocks.products.len()).max(1);Some(FixedRangeProduct::new(blocks.products,level))}else{None};Self{data,block_shift,prefix:blocks.prefix,suffix:blocks.suffix,between}}#[inline]pub fn len(&self)->usize{self.data.len()}#[inline]pub fn is_empty(&self)->bool{self.data.is_empty()}#[inline]pub fn get(&self,index:usize)->&S::T{&self.data[index]}#[inline]pub fn fold(&self,l:usize,r:usize)->S::T{assert!(l<r);assert!(r<=self.data.len());let bl=l>>self.block_shift;let br=(r-1)>>self.block_shift;if bl==br{return fold_slice::<S>(&self.data,l,r);}let mut res=self.suffix[l].clone();if bl+1<br{let mid=self.between.as_ref().expect("middle block product is not built").fold(bl+1,br);res=S::operate(&res,&mid);}S::operate(&res,&self.prefix[r-1])}}#[derive(Clone)]enum FixedRangeProduct<S>where S:SemiGroup{Direct{data:Vec<S::T>},Disjoint{table:DisjointSparseTable<S>},Recursive{data:Vec<S::T>,block_shift:usize,prefix:Vec<S::T>,suffix:Vec<S::T>,between:Box<FixedRangeProduct<S>>}}impl<S>Debug for FixedRangeProduct<S>where S:SemiGroup<T:Debug>{fn fmt(&self,f:&mut Formatter<'_>)->fmt::Result{match self{Self::Direct{data}=>f.debug_struct("Direct").field("data",data).finish(),Self::Disjoint{table}=>f.debug_struct("Disjoint").field("table",table).finish(),Self::Recursive{data,block_shift,prefix,suffix,between}=>f.debug_struct("Recursive").field("data",data).field("block_size",&(1usize<<block_shift)).field("prefix",prefix).field("suffix",suffix).field("between",between).finish(),}}}impl<S>FixedRangeProduct<S>where S:SemiGroup{fn new(data:Vec<S::T>,level:usize)->Self{let n=data.len();if n<=DIRECT_SIZE||level==0{return Self::Direct{data};}if level==1{return Self::Disjoint{table:DisjointSparseTable::new(data)};}let block_shift=scaled_block_shift(alpha_k(level-1,n));let block_size=1usize<<block_shift;if block_size<=1||block_size>=n{return Self::Direct{data};}let blocks=block_products::<S>(&data,block_size);let between=Box::new(Self::new(blocks.products,level-1));Self::Recursive{data,block_shift,prefix:blocks.prefix,suffix:blocks.suffix,between}}#[inline]fn fold(&self,l:usize,r:usize)->S::T{match self{Self::Direct{data}=>fold_slice::<S>(data,l,r),Self::Disjoint{table}=>table.fold(l,r),Self::Recursive{data,block_shift,prefix,suffix,between}=>{let block_shift=*block_shift;let bl=l>>block_shift;let br=(r-1)>>block_shift;if bl==br{return fold_slice::<S>(data,l,r);}let mut res=suffix[l].clone();if bl+1<br{let mid=between.fold(bl+1,br);res=S::operate(&res,&mid);}S::operate(&res,&prefix[r-1])}}}}#[inline]fn fold_slice<S>(data:&[S::T],l:usize,r:usize)->S::T where S:SemiGroup{let mut res=data[l].clone();for x in&data[l+1..r]{res=S::operate(&res,x);}res}fn block_products<S>(data:&[S::T],block_size:usize)->BlockProducts<S::T>where S:SemiGroup{let n=data.len();let mut prefix=data.to_vec();let mut suffix=data.to_vec();let mut products=Vec::with_capacity(n.div_ceil(block_size));for start in(0..n).step_by(block_size){let end=n.min(start+block_size);for i in start+1..end{prefix[i]=S::operate(&prefix[i-1],&data[i]);}for i in(start..end-1).rev(){suffix[i]=S::operate(&data[i],&suffix[i+1]);}products.push(prefix[end-1].clone());}BlockProducts{prefix,suffix,products}}fn alpha_k(k:usize,n:usize)->usize{if k==0{return n.div_ceil(2);}if n<=1{return 0;}let mut x=n;let mut c=0;while x>1{x=alpha_k(k-1,x);c+=1;}c}fn inverse_ackermann(n:usize)->usize{let mut k=0;while alpha_k(k,n)>3{k+=1;}k}fn scaled_block_shift(alpha:usize)->usize{(alpha.max(2)*BLOCK_SCALE).next_power_of_two().trailing_zeros()as usize}}
// codesnip-guard: DisjointSparseTable
#[cfg_attr(any(),rustfmt::skip)]pub use self::disjoint_sparse_table::DisjointSparseTable;#[cfg_attr(any(),rustfmt::skip)]mod disjoint_sparse_table{use super::SemiGroup;use std::{fmt::{self,Debug,Formatter},ops::Index};pub struct DisjointSparseTable<S>where S:SemiGroup{table:Vec<S::T>,offsets:Vec<usize>,len:usize}impl<S>Clone for DisjointSparseTable<S>where S:SemiGroup{fn clone(&self)->Self{Self{table:self.table.clone(),offsets:self.offsets.clone(),len:self.len}}}impl<S>Debug for DisjointSparseTable<S>where S:SemiGroup<T:Debug>{fn fmt(&self,f:&mut Formatter<'_>)->fmt::Result{f.debug_struct("DisjointSparseTable").field("table",&self.table).field("offsets",&self.offsets).field("len",&self.len).finish()}}impl<S>DisjointSparseTable<S>where S:SemiGroup{pub fn new(v:Vec<S::T>)->Self{let n=v.len();let mut levels=1;let mut k=2;while k<n{levels+=1;k*=2;}let mut table=Vec::with_capacity(n*levels);table.extend(v);let mut offsets=vec![0];let mut k=2;while k<n{let offset=table.len();offsets.push(offset);table.extend_from_within(0..n);for i in(0..n).step_by(k*2){for j in(i..n.min(i+k)-1).rev(){let j=offset+j;let x=S::operate(&table[j],&table[j+1]);table[j]=x;}for j in i+k+1..n.min(i+k*2){let j=offset+j;let x=S::operate(&table[j-1],&table[j]);table[j]=x;}}k*=2;}Self{table,offsets,len:n}}#[inline]pub fn height(&self)->usize{self.len}#[inline]fn most_significant_bit_place(x:usize)->Option<usize>{const C:u32=usize::MAX.count_ones();((C-x.leading_zeros())as usize).checked_sub(1)}#[inline]pub fn fold_close(&self,l:usize,r:usize)->S::T{debug_assert!(l<self.height());debug_assert!(r<self.height());debug_assert!(l<=r);if let Some(x)=Self::most_significant_bit_place(l^r){let offset=self.offsets[x];S::operate(&self.table[offset+l],&self.table[offset+r])}else{self.table[l].clone()}}#[inline]pub fn fold(&self,l:usize,r:usize)->S::T{debug_assert!(l<r);self.fold_close(l,r-1)}}impl<S>Index<usize>for DisjointSparseTable<S>where S:SemiGroup{type Output=S::T;#[inline]fn index(&self,index:usize)->&Self::Output{&self.table[index]}}}
// 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{}};}}