// codesnip-guard: BinaryIndexedTree2D
#[cfg_attr(any(),rustfmt::skip)]pub use self::binary_indexed_tree_2d::BinaryIndexedTree2D;#[cfg_attr(any(),rustfmt::skip)]mod binary_indexed_tree_2d{use super::{Group,Monoid};use std::fmt::{self,Debug,Formatter};pub struct BinaryIndexedTree2D<M>where M:Monoid{h:usize,w:usize,bit:Vec<M::T>}impl<M>Clone for BinaryIndexedTree2D<M>where M:Monoid{fn clone(&self)->Self{Self{h:self.h,w:self.w,bit:self.bit.clone()}}}impl<M>Debug for BinaryIndexedTree2D<M>where M:Monoid<T:Debug>{fn fmt(&self,f:&mut Formatter<'_>)->fmt::Result{f.debug_struct("BinaryIndexedTree2D").field("h",&self.h).field("w",&self.w).field("bit",&self.bit).finish()}}impl<M>BinaryIndexedTree2D<M>where M:Monoid{#[inline]pub fn new(h:usize,w:usize)->Self{let bit=vec![M::unit();(h+1)*(w+1)];Self{h,w,bit}}#[inline]#[doc=" fold [0, i) x [0, j)"]pub fn accumulate0(&self,i:usize,j:usize)->M::T{assert!(i<=self.h&&j<=self.w);let mut res=M::unit();let mut a=i;let stride=self.w+1;while a>0{let mut b=j;while b>0{M::operate_assign(&mut res,unsafe{self.bit.get_unchecked(a*stride+b)});b-=b&(!b+1);}a-=a&(!a+1);}res}#[inline]#[doc=" fold [0, i] x [0, j]"]pub fn accumulate(&self,i:usize,j:usize)->M::T{self.accumulate0(i+1,j+1)}#[inline]pub fn update(&mut self,i:usize,j:usize,x:M::T){assert!(i<self.h&&j<self.w);let mut a=i+1;let stride=self.w+1;while a<=self.h{let mut b=j+1;while b<=self.w{M::operate_assign(unsafe{self.bit.get_unchecked_mut(a*stride+b)},&x);b+=b&(!b+1);}a+=a&(!a+1);}}}impl<G>BinaryIndexedTree2D<G>where G:Group{#[inline]#[doc=" 0-indexed [i1, i2) x [j1, j2)"]pub fn fold(&self,i1:usize,j1:usize,i2:usize,j2:usize)->G::T{let mut res=self.accumulate0(i1,j1);G::rinv_operate_assign(&mut res,&self.accumulate0(i1,j2));G::rinv_operate_assign(&mut res,&self.accumulate0(i2,j1));G::operate_assign(&mut res,&self.accumulate0(i2,j2));res}#[inline]pub fn get(&self,i:usize,j:usize)->G::T{self.fold(i,j,i+1,j+1)}#[inline]pub fn set(&mut self,i:usize,j:usize,x:G::T){let y=G::inverse(&self.get(i,j));let z=G::operate(&y,&x);self.update(i,j,z);}}}
// 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{}};}}