// codesnip-guard: sliding_window_aggregation
#[cfg_attr(any(),rustfmt::skip)]pub use self::sliding_window_aggregation::{DequeAggregation,QueueAggregation};#[cfg_attr(any(),rustfmt::skip)]mod sliding_window_aggregation{use super::Monoid;use std::fmt::{self,Debug,Formatter};pub struct QueueAggregation<M>where M:Monoid{front_stack:Vec<(M::T,M::T)>,back_stack:Vec<(M::T,M::T)>}impl<M>Clone for QueueAggregation<M>where M:Monoid{fn clone(&self)->Self{Self{front_stack:self.front_stack.clone(),back_stack:self.back_stack.clone()}}}impl<M>Debug for QueueAggregation<M>where M:Monoid<T:Debug>{fn fmt(&self,f:&mut Formatter<'_>)->fmt::Result{f.debug_struct("QueueAggregation").field("front_stack",&self.front_stack).field("back_stack",&self.back_stack).finish()}}impl<M>Default for QueueAggregation<M>where M:Monoid{fn default()->Self{Self{front_stack:Vec::new(),back_stack:Vec::new()}}}impl<M>QueueAggregation<M>where M:Monoid{pub fn new()->Self{Self::default()}pub fn len(&self)->usize{self.front_stack.len()+self.back_stack.len()}pub fn is_empty(&self)->bool{self.front_stack.is_empty()&&self.back_stack.is_empty()}pub fn fold_all(&self)->M::T{M::operate(self.front_stack.last().map(|t|&t.0).unwrap_or(&M::unit()),self.back_stack.last().map(|t|&t.0).unwrap_or(&M::unit()))}pub fn last(&self)->Option<&M::T>{self.back_stack.last().or_else(| |self.front_stack.first()).map(|t|&t.1)}pub fn push(&mut self,value:M::T){let x=M::operate(self.back_stack.last().map(|t|&t.0).unwrap_or(&M::unit()),&value);self.back_stack.push((x,value));}fn push_front(&mut self,value:M::T){let x=M::operate(&value,self.front_stack.last().map(|t|&t.0).unwrap_or(&M::unit()));self.front_stack.push((x,value));}pub fn pop(&mut self)->Option<M::T>{if self.front_stack.is_empty(){let mut back_stack=std::mem::take(&mut self.back_stack);for x in back_stack.drain(..).map(|t|t.1).rev(){self.push_front(x);}self.back_stack=back_stack;}self.front_stack.pop().map(|t|t.1)}}pub struct DequeAggregation<M>where M:Monoid{front_stack:Vec<(M::T,M::T)>,back_stack:Vec<(M::T,M::T)>}impl<M>Clone for DequeAggregation<M>where M:Monoid{fn clone(&self)->Self{Self{front_stack:self.front_stack.clone(),back_stack:self.back_stack.clone()}}}impl<M>Debug for DequeAggregation<M>where M:Monoid<T:Debug>{fn fmt(&self,f:&mut Formatter<'_>)->fmt::Result{f.debug_struct("DequeAggregation").field("front_stack",&self.front_stack).field("back_stack",&self.back_stack).finish()}}impl<M>Default for DequeAggregation<M>where M:Monoid{fn default()->Self{Self{front_stack:Vec::new(),back_stack:Vec::new()}}}impl<M>DequeAggregation<M>where M:Monoid{pub fn new()->Self{Self::default()}pub fn len(&self)->usize{self.front_stack.len()+self.back_stack.len()}pub fn is_empty(&self)->bool{self.front_stack.is_empty()&&self.back_stack.is_empty()}pub fn fold_all(&self)->M::T{M::operate(self.front_stack.last().map(|t|&t.0).unwrap_or(&M::unit()),self.back_stack.last().map(|t|&t.0).unwrap_or(&M::unit()))}pub fn front(&self)->Option<&M::T>{self.front_stack.last().or_else(| |self.back_stack.first()).map(|t|&t.1)}pub fn back(&self)->Option<&M::T>{self.back_stack.last().or_else(| |self.front_stack.first()).map(|t|&t.1)}pub fn push_front(&mut self,value:M::T){let x=M::operate(&value,self.front_stack.last().map(|t|&t.0).unwrap_or(&M::unit()));self.front_stack.push((x,value));}pub fn push_back(&mut self,value:M::T){let x=M::operate(self.back_stack.last().map(|t|&t.0).unwrap_or(&M::unit()),&value);self.back_stack.push((x,value));}pub fn pop_front(&mut self)->Option<M::T>{if self.front_stack.is_empty(){let n=self.back_stack.len();let mut back_stack=std::mem::take(&mut self.back_stack);for x in back_stack.drain(..n.div_ceil(2)).map(|t|t.1).rev(){self.push_front(x);}for x in back_stack.drain(..).map(|t|t.1){self.push_back(x);}}self.front_stack.pop().map(|t|t.1)}pub fn pop_back(&mut self)->Option<M::T>{if self.back_stack.is_empty(){let n=self.front_stack.len();let mut front_stack=std::mem::take(&mut self.front_stack);for x in front_stack.drain(..n.div_ceil(2)).map(|t|t.1).rev(){self.push_back(x);}for x in front_stack.drain(..).map(|t|t.1){self.push_front(x);}}self.back_stack.pop().map(|t|t.1)}}}
// 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{}};}}