// codesnip-guard: PairingHeap
#[cfg_attr(any(),rustfmt::skip)]pub use self::pairing_heap::PairingHeap;#[cfg_attr(any(),rustfmt::skip)]mod pairing_heap{use super::{Comparator,EmptyAct,MonoidAct,Unital,comparator::Less};use std::{cmp::Ordering,fmt::{self,Debug,Formatter},iter::FusedIterator,mem::{replace,swap},ops::{Deref,DerefMut}};#[derive(Clone)]struct Node<T,A>where A:MonoidAct<Key=T,Act:PartialEq>{value:T,first_child:Option<Box<Node<T,A>>>,next_sibling:Option<Box<Node<T,A>>>,lazy:A::Act}impl<T,A>Node<T,A>where A:MonoidAct<Key=T,Act:PartialEq>{fn new(value:T)->Self{Self{value,first_child:None,next_sibling:None,lazy:A::unit()}}fn apply(&mut self,act:&A::Act){A::act_assign(&mut self.value,act);A::operate_assign(&mut self.lazy,act);}fn propagate(&mut self){if!<A::ActMonoid as Unital>::is_unit(&self.lazy){let act=replace(&mut self.lazy,A::unit());if let Some(node)=self.first_child.as_mut(){node.apply(&act);}if let Some(node)=self.next_sibling.as_mut(){node.apply(&act);}}}}impl<T,A>Debug for Node<T,A>where T:Debug,A:MonoidAct<Key=T,Act:PartialEq+Debug>{fn fmt(&self,f:&mut Formatter<'_>)->fmt::Result{f.debug_struct("Node").field("value",&self.value).field("first_child",&self.first_child).field("next_sibling",&self.next_sibling).field("lazy",&self.lazy).finish()}}#[derive(Clone)]pub struct PairingHeap<T,C=Less,A=EmptyAct<T>>where A:MonoidAct<Key=T,Act:PartialEq>{root:Option<Box<Node<T,A>>>,len:usize,cmp:C}impl<T,C,A>PairingHeap<T,C,A>where C:Comparator<T>,A:MonoidAct<Key=T,Act:PartialEq>{pub fn with_comparator(cmp:C)->Self{Self{root:None,len:0,cmp}}pub fn len(&self)->usize{self.len}pub fn is_empty(&self)->bool{self.len==0}pub fn peek(&self)->Option<&T>{self.root.as_ref().map(|node|&node.value)}pub fn push(&mut self,value:T){let node=Box::new(Node::new(value));let root=self.root.take();self.root=self.merge_option(root,Some(node));self.len+=1;}pub fn append(&mut self,other:&mut Self){if other.is_empty(){return;}let left=self.root.take();self.root=self.merge_option(left,other.root.take());self.len+=other.len;other.len=0;}pub fn pop(&mut self)->Option<T>{self.root.take().map(|mut root|{self.len-=1;root.propagate();let children=root.first_child.take();self.root=self.merge_pairs(children);root.value})}pub fn peek_mut(&mut self)->Option<PeekMut<'_,T,C,A>>{let mut root=self.root.take()?;root.propagate();let children=root.first_child.take();debug_assert!(root.next_sibling.is_none());root.next_sibling=None;self.root=self.merge_pairs(children);Some(PeekMut{heap:self,node:Some(root)})}pub fn clear(&mut self){self.root=None;self.len=0;}pub fn apply_all(&mut self,act:A::Act){if let Some(root)=self.root.as_mut(){root.apply(&act);}}pub fn into_sorted_vec(mut self)->Vec<T>{let mut result=Vec::with_capacity(self.len);while let Some(value)=self.pop(){result.push(value);}result}fn merge_option(&mut self,a:Option<Box<Node<T,A>>>,b:Option<Box<Node<T,A>>>)->Option<Box<Node<T,A>>>{match(a,b){(None,None)=>None,(Some(node),None)|(None,Some(node))=>Some(node),(Some(mut a),Some(mut b))=>{a.propagate();b.propagate();if self.cmp.compare(&a.value,&b.value)==Ordering::Greater{swap(&mut a,&mut b);}b.next_sibling=a.first_child.take();a.first_child=Some(b);Some(a)}}}fn merge_pairs(&mut self,mut head:Option<Box<Node<T,A>>>)->Option<Box<Node<T,A>>>{let mut pairs=None;while let Some(mut first)=head{first.propagate();let next=first.next_sibling.take();let mut pair=if let Some(mut second)=next{second.propagate();head=second.next_sibling.take();self.merge_option(Some(first),Some(second)).unwrap()}else{head=None;first};pair.next_sibling=pairs;pairs=Some(pair);}let mut result=None;while let Some(mut node)=pairs{pairs=node.next_sibling.take();result=self.merge_option(Some(node),result);}result}}impl<T,C,A>Default for PairingHeap<T,C,A>where C:Comparator<T>+Default,A:MonoidAct<Key=T,Act:PartialEq>{fn default()->Self{Self::with_comparator(C::default())}}impl<T,A>PairingHeap<T,Less,A>where T:Ord,A:MonoidAct<Key=T,Act:PartialEq>{pub fn new()->Self{Self::default()}}impl<T,C,A>Debug for PairingHeap<T,C,A>where T:Debug,C:Debug+Comparator<T>,A:MonoidAct<Key=T,Act:PartialEq+Debug>{fn fmt(&self,f:&mut Formatter<'_>)->fmt::Result{f.debug_struct("PairingHeap").field("len",&self.len).field("root",&self.root).field("cmp",&self.cmp).finish()}}impl<T,C,A>Extend<T>for PairingHeap<T,C,A>where C:Comparator<T>,A:MonoidAct<Key=T,Act:PartialEq>{fn extend<I:IntoIterator<Item=T>>(&mut self,iter:I){for value in iter{self.push(value);}}}impl<T,C,A>FromIterator<T>for PairingHeap<T,C,A>where C:Comparator<T>+Default,A:MonoidAct<Key=T,Act:PartialEq>{fn from_iter<I:IntoIterator<Item=T>>(iter:I)->Self{let mut heap=Self::default();heap.extend(iter);heap}}pub struct PeekMut<'a,T,C=Less,A=EmptyAct<T>>where C:Comparator<T>,A:MonoidAct<Key=T,Act:PartialEq>{heap:&'a mut PairingHeap<T,C,A>,node:Option<Box<Node<T,A>>>}impl<'a,T,C,A>PeekMut<'a,T,C,A>where C:Comparator<T>,A:MonoidAct<Key=T,Act:PartialEq>{pub fn pop(mut this:Self)->T{this.heap.len-=1;let node=this.node.take().expect("PeekMut already consumed");let Node{value,..}=*node;value}}impl<'a,T,C,A>Deref for PeekMut<'a,T,C,A>where C:Comparator<T>,A:MonoidAct<Key=T,Act:PartialEq>{type Target=T;fn deref(&self)->&Self::Target{&self.node.as_ref().expect("PeekMut already consumed").value}}impl<'a,T,C,A>DerefMut for PeekMut<'a,T,C,A>where C:Comparator<T>,A:MonoidAct<Key=T,Act:PartialEq>{fn deref_mut(&mut self)->&mut Self::Target{&mut self.node.as_mut().expect("PeekMut already consumed").value}}impl<'a,T,C,A>Drop for PeekMut<'a,T,C,A>where C:Comparator<T>,A:MonoidAct<Key=T,Act:PartialEq>{fn drop(&mut self){if let Some(mut node)=self.node.take(){debug_assert!(node.next_sibling.is_none());let root=self.heap.root.take();node.first_child=None;self.heap.root=self.heap.merge_option(root,Some(node));}}}pub struct IntoIter<T,C=Less,A=EmptyAct<T>>where C:Comparator<T>,A:MonoidAct<Key=T,Act:PartialEq>{heap:PairingHeap<T,C,A>}impl<T,C,A>IntoIter<T,C,A>where C:Comparator<T>,A:MonoidAct<Key=T,Act:PartialEq>{fn new(heap:PairingHeap<T,C,A>)->Self{Self{heap}}}impl<T,C,A>Iterator for IntoIter<T,C,A>where C:Comparator<T>,A:MonoidAct<Key=T,Act:PartialEq>{type Item=T;fn next(&mut self)->Option<Self::Item>{self.heap.pop()}fn size_hint(&self)->(usize,Option<usize>){let len=self.heap.len();(len,Some(len))}}impl<T,C,A>ExactSizeIterator for IntoIter<T,C,A>where C:Comparator<T>,A:MonoidAct<Key=T,Act:PartialEq>{fn len(&self)->usize{self.heap.len()}}impl<T,C,A>FusedIterator for IntoIter<T,C,A>where C:Comparator<T>,A:MonoidAct<Key=T,Act:PartialEq>{}impl<T,C,A>IntoIterator for PairingHeap<T,C,A>where C:Comparator<T>,A:MonoidAct<Key=T,Act:PartialEq>{type Item=T;type IntoIter=IntoIter<T,C,A>;fn into_iter(self)->Self::IntoIter{IntoIter::new(self)}}}
// codesnip-guard: Comparator
#[cfg_attr(any(),rustfmt::skip)]pub use self::comparator::Comparator;#[cfg_attr(any(),rustfmt::skip)]pub mod comparator{use std::cmp::Ordering;pub trait Comparator<T>{fn compare(&mut self,a:&T,b:&T)->Ordering;}impl<T,F>Comparator<T>for F where F:FnMut(&T,&T)->Ordering{fn compare(&mut self,a:&T,b:&T)->Ordering{(self)(a,b)}}#[derive(Debug,Clone,Copy,Default,PartialEq,Eq,PartialOrd,Ord,Hash)]pub struct Less;impl<T>Comparator<T>for Less where T:Ord{fn compare(&mut self,a:&T,b:&T)->Ordering{a.cmp(b)}}#[derive(Debug,Clone,Copy,Default,PartialEq,Eq,PartialOrd,Ord,Hash)]pub struct Greater;impl<T>Comparator<T>for Greater where T:Ord{fn compare(&mut self,a:&T,b:&T)->Ordering{b.cmp(a)}}#[derive(Debug,Clone,Copy,Default,PartialEq,Eq,PartialOrd,Ord,Hash)]pub struct ByKey<F>(pub F);impl<T,F,K>Comparator<T>for ByKey<F>where F:FnMut(&T)->K,K:Ord{fn compare(&mut self,a:&T,b:&T)->Ordering{(self.0)(a).cmp(&(self.0)(b))}}}
// codesnip-guard: LastOperation
#[cfg_attr(any(),rustfmt::skip)]pub use self::last_operation_impl::LastOperation;#[cfg_attr(any(),rustfmt::skip)]mod last_operation_impl{use super::*;use std::marker::PhantomData;#[doc=" retain the last element"]pub struct LastOperation<T>where T:Clone{_marker:PhantomData<fn()->T>}impl<T>Magma for LastOperation<T>where T:Clone{type T=Option<T>;#[inline]fn operate(x:&Self::T,y:&Self::T)->Self::T{y.as_ref().or(x.as_ref()).cloned()}}impl<T>Unital for LastOperation<T>where T:Clone{#[inline]fn unit()->Self::T{None}}impl<T>Associative for LastOperation<T>where T:Clone{}impl<T>Idempotent for LastOperation<T>where T:Clone{}}
// codesnip-guard: LinearOperation
#[cfg_attr(any(),rustfmt::skip)]pub use self::linear_operation_impl::LinearOperation;#[cfg_attr(any(),rustfmt::skip)]mod linear_operation_impl{use super::*;use std::{marker::PhantomData,ops::{Add,Div,Mul,Neg,Sub}};#[doc=" $(a, b) \\circ (c, d) = \\lambda x. c \\times (a \\times x + b) + d$"]pub struct LinearOperation<T>where T:Clone+Zero+Add<Output=T>+One+Mul<Output=T>{_marker:PhantomData<fn()->T>}impl<T>LinearOperation<T>where T:Clone+Zero+Add<Output=T>+One+Mul<Output=T>{pub fn apply(f:&(T,T),x:&T)->T{f.0 .clone()*x.clone()+f.1 .clone()}}impl<T>Magma for LinearOperation<T>where T:Clone+Zero+One+Add<Output=T>+Mul<Output=T>{type T=(T,T);#[inline]fn operate(x:&Self::T,y:&Self::T)->Self::T{(y.0 .clone()*x.0 .clone(),y.0 .clone()*x.1 .clone()+y.1 .clone())}}impl<T>Unital for LinearOperation<T>where T:Clone+Zero+One+Add<Output=T>+Mul<Output=T>{#[inline]fn unit()->Self::T{(One::one(),Zero::zero())}}impl<T>Associative for LinearOperation<T>where T:Clone+Zero+One+Add<Output=T>+Mul<Output=T>{}impl<T>Invertible for LinearOperation<T>where T:Clone+Zero+One+Add<Output=T>+Sub<Output=T>+Neg<Output=T>+Mul<Output=T>+Div<Output=T>{fn inverse(x:&Self::T)->Self::T{let y=<T as One>::one().div(x.0 .clone());(y.clone(),-y.mul(x.1 .clone()))}}}
// codesnip-guard: MonoidAct
#[cfg_attr(any(),rustfmt::skip)]pub use self::action::*;#[cfg_attr(any(),rustfmt::skip)]mod action{use super::*;use std::{marker::PhantomData,ops::{Add,Mul}};pub trait MonoidAct{type Key;type Act:Clone;type ActMonoid:Monoid<T=Self::Act>;fn act(x:&Self::Key,a:&Self::Act)->Self::Key;fn act_assign(x:&mut Self::Key,a:&Self::Act){*x=Self::act(x,a);}fn unit()->Self::Act{<Self::ActMonoid as Unital>::unit()}fn operate(x:&Self::Act,y:&Self::Act)->Self::Act{<Self::ActMonoid as Magma>::operate(x,y)}fn operate_assign(x:&mut Self::Act,y:&Self::Act){*x=<Self::ActMonoid as Magma>::operate(x,y);}}pub struct EmptyAct<T>{_marker:PhantomData<fn()->T>}impl<T>MonoidAct for EmptyAct<T>where T:Clone{type Key=T;type Act=();type ActMonoid=();fn act(x:&Self::Key,_a:&Self::Act)->Self::Key{x.clone()}}pub struct FlattenAct<M>{_marker:PhantomData<fn()->M>}impl<M>MonoidAct for FlattenAct<M>where M:Monoid{type Key=M::T;type Act=M::T;type ActMonoid=M;fn act(x:&Self::Key,a:&Self::Act)->Self::Key{M::operate(x,a)}}pub struct LinearAct<T>{_marker:PhantomData<fn()->T>}impl<T>MonoidAct for LinearAct<T>where T:Clone+Zero+One+Add<Output=T>+Mul<Output=T>{type Key=T;type Act=(T,T);type ActMonoid=LinearOperation<T>;fn act(x:&Self::Key,(a,b):&Self::Act)->Self::Key{a.clone()*x.clone()+b.clone()}}pub struct UpdateAct<T>{_marker:PhantomData<fn()->T>}impl<T>MonoidAct for UpdateAct<T>where T:Clone{type Key=T;type Act=Option<T>;type ActMonoid=LastOperation<T>;fn act(x:&Self::Key,a:&Self::Act)->Self::Key{a.as_ref().unwrap_or(x).clone()}}}
// codesnip-guard: TupleOperation
#[cfg_attr(any(),rustfmt::skip)]mod tuple_operation_impl{use super::*;macro_rules!impl_tuple_operation{(@impl)=>{impl Magma for(){type T=();fn operate(_x:&Self::T,_y:&Self::T)->Self::T{}}impl Unital for(){fn unit()->Self::T{}}impl Associative for(){}impl Commutative for(){}impl Idempotent for(){}impl Invertible for(){fn inverse(_x:&Self::T)->Self::T{}}};(@impl$($T:ident$i:tt)*)=>{impl<$($T:Magma),*>Magma for($($T,)*){type T=($(<$T as Magma>::T,)*);fn operate(x:&Self::T,y:&Self::T)->Self::T{($(<$T as Magma>::operate(&x.$i,&y.$i),)*)}}impl<$($T:Unital),*>Unital for($($T,)*){fn unit()->Self::T{($(<$T as Unital>::unit(),)*)}}impl<$($T:Associative),*>Associative for($($T,)*){}impl<$($T:Commutative),*>Commutative for($($T,)*){}impl<$($T:Idempotent),*>Idempotent for($($T,)*){}impl<$($T:Invertible),*>Invertible for($($T,)*){fn inverse(x:&Self::T)->Self::T{($(<$T as Invertible>::inverse(&x.$i),)*)}}};(@inner$($T:ident$i:tt)*;$U:ident$j:tt$($t:tt)*)=>{impl_tuple_operation!(@impl$($T$i)*);impl_tuple_operation!(@inner$($T$i)*$U$j;$($t)*);};(@inner$($T:ident$i:tt)*;)=>{impl_tuple_operation!(@impl$($T$i)*);};($($t:tt)*)=>{impl_tuple_operation!(@inner;$($t)*);};}impl_tuple_operation!(A 0 B 1 C 2 D 3 E 4 F 5 G 6 H 7 I 8 J 9);}
// 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: zero_one
#[cfg_attr(any(),rustfmt::skip)]pub use self::zero_one::{One,Zero};#[cfg_attr(any(),rustfmt::skip)]mod zero_one{pub trait Zero:Sized{fn zero()->Self;#[inline]fn is_zero(&self)->bool where Self:PartialEq{self==&Self::zero()}#[inline]fn set_zero(&mut self){*self=Self::zero();}}pub trait One:Sized{fn one()->Self;#[inline]fn is_one(&self)->bool where Self:PartialEq{self==&Self::one()}#[inline]fn set_one(&mut self){*self=Self::one();}}macro_rules!impl_zero_one{($({$(<$T:ident:$Bound:ident>)?$Trait:ident$method:ident$($t:ty)*,$e:expr})*)=>{$(impl_zero_one!(@impl[$(<$T:$Bound>)?]$Trait$method[$($t)*],$e);)*};(@impl[<$T:ident:$Bound:ident>]$Trait:ident$method:ident[$($t:ty)*],$e:expr)=>{$(impl<$T:$Bound>$Trait for$t{fn$method()->Self{$e}})*};(@impl[]$Trait:ident$method:ident[$($t:ty)*],$e:expr)=>{$(impl$Trait for$t{fn$method()->Self{$e}})*};}impl_zero_one!({Zero zero u8 u16 u32 u64 usize i8 i16 i32 i64 isize u128 i128,0}{Zero zero f32 f64,0.}{One one u8 u16 u32 u64 usize i8 i16 i32 i64 isize u128 i128,1}{One one f32 f64,1.}{<T:Zero>Zero zero std::num::Wrapping<T>,Self(T::zero())}{<T:One>One one std::num::Wrapping<T>,Self(T::one())});}