// codesnip-guard: shortest_path
#[cfg_attr(any(),rustfmt::skip)]pub use self::shortest_path::{ShortestPathExt,ShortestPathSemiRing};#[cfg_attr(any(),rustfmt::skip)]pub mod shortest_path{use super::*;use std::{cmp::{Ordering,Reverse},collections::{BinaryHeap,VecDeque},marker::PhantomData,ops::Add};pub trait ShortestPathSemiRing{type T:Clone+Ord;fn source()->Self::T;fn inf()->Self::T;fn mul(x:&Self::T,y:&Self::T)->Self::T;fn add_assign(x:&mut Self::T,y:&Self::T)->bool;}pub struct StandardSp<M>(PhantomData<fn()->M>);impl<M>ShortestPathSemiRing for StandardSp<M>where M:Monoid<T:Bounded+Ord>{type T=M::T;#[inline]fn source()->Self::T{M::unit()}#[inline]fn inf()->Self::T{M::T::maximum()}#[inline]fn mul(x:&Self::T,y:&Self::T)->Self::T{M::operate(x,y)}#[inline]fn add_assign(x:&mut Self::T,y:&Self::T)->bool{if&*x>y{*x=y.clone();true}else{false}}}pub struct OptionSp<M>(PhantomData<fn()->M>);impl<M>ShortestPathSemiRing for OptionSp<M>where M:Monoid<T:Ord>{type T=Option<M::T>;#[inline]fn source()->Self::T{Some(M::unit())}#[inline]fn inf()->Self::T{None}#[inline]fn mul(x:&Self::T,y:&Self::T)->Self::T{match(x,y){(Some(x),Some(y))=>Some(M::operate(x,y)),_=>None,}}#[inline]fn add_assign(x:&mut Self::T,y:&Self::T)->bool{if let Some(y)=y{if let Some(x)=x{if&*x>y{*x=y.clone();true}else{false}}else{*x=Some(y.clone());true}}else{false}}}pub struct PathFoldingSp<M,S>(PhantomData<fn()->(M,S)>);impl<M,S>ShortestPathSemiRing for PathFoldingSp<M,S>where M:Monoid<T:Bounded+Ord>,S:SemiRing{type T=PartialIgnoredOrd<M::T,S::T>;#[inline]fn source()->Self::T{PartialIgnoredOrd(M::unit(),S::one())}#[inline]fn inf()->Self::T{PartialIgnoredOrd(M::T::maximum(),S::zero())}#[inline]fn mul(x:&Self::T,y:&Self::T)->Self::T{PartialIgnoredOrd(M::operate(&x.0,&y.0),S::mul(&x.1,&y.1))}#[inline]fn add_assign(x:&mut Self::T,y:&Self::T)->bool{match x.0 .cmp(&y.0){Ordering::Equal=>{x.1=S::add(&x.1,&y.1);false}Ordering::Greater=>{*x=y.clone();true}_=>false,}}}pub trait ParentPolicy<G>where G:Graph{type State;fn init(graph:&G)->Self::State;fn save_parent(graph:&G,state:&mut Self::State,from:G::Vertex,to:G::Vertex);}pub enum NoParent{}impl<G>ParentPolicy<G>for NoParent where G:Graph{type State=();fn init(_graph:&G){}fn save_parent(_graph:&G,_state:&mut Self::State,_from:G::Vertex,_to:G::Vertex){}}pub struct RecordParent;impl<G>ParentPolicy<G>for RecordParent where G:Graph+VertexMap<Option<<G as Graph>::Vertex>>{type State=<G as VertexMap<Option<<G as Graph>::Vertex>>>::Vmap;fn init(graph:&G)->Self::State{graph.construct_vmap(| |None)}fn save_parent(graph:&G,state:&mut Self::State,from:G::Vertex,to:G::Vertex){*graph.vmap_get_mut(state,to)=Some(from);}}pub struct ShortestPathWithParent<G,S,P=RecordParent>where G:Graph+VertexMap<S::T>,S:ShortestPathSemiRing,P:ParentPolicy<G>{pub dist:<G as VertexMap<S::T>>::Vmap,pub parent:P::State}impl<G,S>ShortestPathWithParent<G,S,RecordParent>where G:Graph+VertexMap<S::T>+VertexMap<Option<<G as Graph>::Vertex>>,S:ShortestPathSemiRing{pub fn path_to(&self,graph:&G,target:G::Vertex)->Option<Vec<G::Vertex>>{let dist:&S::T=graph.vmap_get(&self.dist,target);if dist==&S::inf(){return None;}let mut cur=target;let mut path=vec![cur];while let&Some(p)=graph.vmap_get(&self.parent,cur){path.push(p);cur=p;}path.reverse();Some(path)}}pub trait ShortestPathExt:Graph{fn standard_sp<'a,M>(&'a self)->ShortestPathBuilder<'a,Self,StandardSp<M>>where Self:Sized,M:Monoid<T:Bounded+Ord>{ShortestPathBuilder{graph:self,_marker:PhantomData}}fn standard_sp_additive<'a,T>(&'a self)->ShortestPathBuilder<'a,Self,StandardSp<AdditiveOperation<T>>>where Self:Sized,T:Clone+Zero+Add<Output=T>+Bounded+Ord{ShortestPathBuilder{graph:self,_marker:PhantomData}}fn option_sp<'a,M>(&'a self)->ShortestPathBuilder<'a,Self,OptionSp<M>>where Self:Sized,M:Monoid<T:Ord>{ShortestPathBuilder{graph:self,_marker:PhantomData}}fn option_sp_additive<'a,T>(&'a self)->ShortestPathBuilder<'a,Self,OptionSp<AdditiveOperation<T>>>where Self:Sized,T:Clone+Zero+Add<Output=T>+Ord{ShortestPathBuilder{graph:self,_marker:PhantomData}}fn path_folding_sp<'a,M,S>(&'a self)->ShortestPathBuilder<'a,Self,PathFoldingSp<M,S>>where Self:Sized,M:Monoid<T:Bounded+Ord>,S:SemiRing{ShortestPathBuilder{graph:self,_marker:PhantomData}}fn path_folding_sp_additive_addmul<'a,T,U>(&'a self)->ShortestPathBuilder<'a,Self,PathFoldingSp<AdditiveOperation<T>,AddMulOperation<U>>>where Self:Sized,T:Clone+Zero+Add<Output=T>+Bounded+Ord,U:DotProduct+One{ShortestPathBuilder{graph:self,_marker:PhantomData}}}impl<G>ShortestPathExt for G where G:Graph+?Sized{}pub struct ShortestPathBuilder<'a,G,S,P=NoParent>where G:Graph,S:ShortestPathSemiRing,P:ParentPolicy<G>{graph:&'a G,_marker:PhantomData<fn()->(S,P)>}impl<'a,G,S,P>ShortestPathBuilder<'a,G,S,P>where G:Graph,S:ShortestPathSemiRing,P:ParentPolicy<G>{fn bfs_distance_core<M,I>(&self,sources:I,weight:&M)->ShortestPathWithParent<G,S,P>where G:VertexMap<S::T>,M:Fn(G::Label)->S::T+?Sized,I:IntoIterator<Item=G::Vertex>{let graph=self.graph;let mut dist=graph.construct_vmap(S::inf);let mut parent=P::init(graph);let mut deq=VecDeque::new();for source in sources.into_iter(){*graph.vmap_get_mut(&mut dist,source)=S::source();deq.push_back(source);}let zero=S::source();while let Some(u)=deq.pop_front(){for neighbor in graph.neighbors(u){let v=neighbor.to;let w=weight(neighbor.label);let nd=S::mul(graph.vmap_get(&dist,u),&w);if S::add_assign(graph.vmap_get_mut(&mut dist,v),&nd){P::save_parent(graph,&mut parent,u,v);if w==zero{deq.push_front(v);}else{deq.push_back(v);}}}}ShortestPathWithParent{dist,parent}}fn dijkstra_core<M,I>(&self,sources:I,weight:&M,mut stop:impl FnMut(G::Vertex)->bool)->ShortestPathWithParent<G,S,P>where G:VertexMap<S::T>,M:Fn(G::Label)->S::T+?Sized,I:IntoIterator<Item=G::Vertex>{let graph=self.graph;let mut dist=graph.construct_vmap(S::inf);let mut parent=P::init(graph);let mut heap=BinaryHeap::new();for source in sources.into_iter(){*graph.vmap_get_mut(&mut dist,source)=S::source();heap.push(PartialIgnoredOrd(Reverse(S::source()),source));}while let Some(PartialIgnoredOrd(Reverse(d),u))=heap.pop(){let current=graph.vmap_get(&dist,u);if current!=&d{continue;}if stop(u){break;}let d=current.clone();for neighbor in graph.neighbors(u){let v=neighbor.to;let weight=weight(neighbor.label);let nd=S::mul(&d,&weight);if S::add_assign(graph.vmap_get_mut(&mut dist,v),&nd){P::save_parent(graph,&mut parent,u,v);heap.push(PartialIgnoredOrd(Reverse(nd),v));}}}ShortestPathWithParent{dist,parent}}fn bellman_ford_core<M,I>(&self,sources:I,weight:&M,check:bool)->Option<ShortestPathWithParent<G,S,P>>where G:VertexMap<S::T>,M:Fn(G::Label)->S::T+?Sized,I:IntoIterator<Item=G::Vertex>,P:ParentPolicy<G>{let graph=self.graph;let mut dist=graph.construct_vmap(S::inf);let mut parent=P::init(graph);for source in sources.into_iter(){*graph.vmap_get_mut(&mut dist,source)=S::source();}let vsize=graph.vsize();for _ in 1..vsize{let mut updated=false;for u in graph.vertices(){for neighbor in graph.neighbors(u){let v=neighbor.to;let weight=weight(neighbor.label);let nd=S::mul(graph.vmap_get(&dist,u),&weight);if S::add_assign(graph.vmap_get_mut(&mut dist,v),&nd){P::save_parent(graph,&mut parent,u,v);updated=true;}}}if!updated{break;}}if check{for u in graph.vertices(){for neighbor in graph.neighbors(u){let v=neighbor.to;let weight=weight(neighbor.label);let nd=S::mul(graph.vmap_get(&dist,u),&weight);if S::add_assign(graph.vmap_get_mut(&mut dist,v),&nd){return None;}}}}Some(ShortestPathWithParent{dist,parent})}}impl<'a,G,S>ShortestPathBuilder<'a,G,S,NoParent>where G:Graph,S:ShortestPathSemiRing{pub fn with_parent(self)->ShortestPathBuilder<'a,G,S,RecordParent>where G:VertexMap<Option<<G as Graph>::Vertex>>{ShortestPathBuilder{graph:self.graph,_marker:PhantomData}}pub fn bfs_distance<M,I>(&self,sources:I,weight:M)-><G as VertexMap<S::T>>::Vmap where G:VertexMap<S::T>,M:Fn(G::Label)->S::T,I:IntoIterator<Item=G::Vertex>{self.bfs_distance_core(sources,&weight).dist}pub fn dijkstra<M,I>(&self,sources:I,weight:M)-><G as VertexMap<S::T>>::Vmap where G:VertexMap<S::T>,M:Fn(G::Label)->S::T,I:IntoIterator<Item=G::Vertex>{self.dijkstra_core(sources,&weight,|_|false).dist}pub fn bellman_ford<M,I>(&self,sources:I,weight:M,check:bool)->Option<<G as VertexMap<S::T>>::Vmap>where G:VertexMap<S::T>,M:Fn(G::Label)->S::T,I:IntoIterator<Item=G::Vertex>{self.bellman_ford_core(sources,&weight,check).map(|sp|sp.dist)}pub fn warshall_floyd_ap<M>(&self,weight:M)-><G as VertexMap<<G as VertexMap<S::T>>::Vmap>>::Vmap where G:VertexMap<S::T,Vmap:Clone>+VertexMap<<G as VertexMap<S::T>>::Vmap>,M:Fn(G::Label)->S::T{let graph=self.graph;let mut dist=graph.construct_vmap(| |graph.construct_vmap(S::inf));for u in graph.vertices(){*graph.vmap_get_mut(graph.vmap_get_mut(&mut dist,u),u)=S::source();}for u in graph.vertices(){for neighbor in graph.neighbors(u){let weight=weight(neighbor.label);S::add_assign(graph.vmap_get_mut(graph.vmap_get_mut(&mut dist,u),neighbor.to),&weight);}}for k in graph.vertices(){for i in graph.vertices(){for j in graph.vertices(){let d1=graph.vmap_get(graph.vmap_get(&dist,i),k);let d2=graph.vmap_get(graph.vmap_get(&dist,k),j);let nd=S::mul(d1,d2);S::add_assign(graph.vmap_get_mut(graph.vmap_get_mut(&mut dist,i),j),&nd);}}}dist}}impl<'a,G,S>ShortestPathBuilder<'a,G,S,RecordParent>where G:Graph+VertexMap<Option<<G as Graph>::Vertex>>,S:ShortestPathSemiRing{pub fn bfs_distance<M,I>(&self,sources:I,weight:M)->ShortestPathWithParent<G,S>where G:VertexMap<S::T>,M:Fn(G::Label)->S::T,I:IntoIterator<Item=G::Vertex>{self.bfs_distance_core(sources,&weight)}pub fn dijkstra<M,I>(&self,sources:I,weight:M)->ShortestPathWithParent<G,S>where G:VertexMap<S::T>,M:Fn(G::Label)->S::T,I:IntoIterator<Item=G::Vertex>{self.dijkstra_core(sources,&weight,|_|false)}pub fn bellman_ford<M,I>(&self,sources:I,weight:M,check:bool)->Option<ShortestPathWithParent<G,S>>where G:VertexMap<S::T>,M:Fn(G::Label)->S::T,I:IntoIterator<Item=G::Vertex>{self.bellman_ford_core(sources,&weight,check)}}impl<'a,G,M,P>ShortestPathBuilder<'a,G,StandardSp<M>,P>where G:Graph,M:Monoid<T:Bounded+Ord>,P:ParentPolicy<G>{#[doc=" Distances other than the target may remain tentative."]pub fn dijkstra_to<W,I>(&self,sources:I,target:G::Vertex,weight:W)->ShortestPathWithParent<G,StandardSp<M>,P>where G:VertexMap<M::T>,W:Fn(G::Label)->M::T,I:IntoIterator<Item=G::Vertex>{self.dijkstra_core(sources,&weight,|u|u==target)}}}
// codesnip-guard: AdditiveOperation
#[cfg_attr(any(),rustfmt::skip)]pub use self::additive_operation_impl::AdditiveOperation;#[cfg_attr(any(),rustfmt::skip)]mod additive_operation_impl{use super::*;use std::{marker::PhantomData,ops::{Add,Neg,Sub}};#[doc=" $+$"]pub struct AdditiveOperation<T>where T:Clone+Zero+Add<Output=T>{_marker:PhantomData<fn()->T>}impl<T>Magma for AdditiveOperation<T>where T:Clone+Zero+Add<Output=T>{type T=T;#[inline]fn operate(x:&Self::T,y:&Self::T)->Self::T{x.clone()+y.clone()}}impl<T>Unital for AdditiveOperation<T>where T:Clone+Zero+Add<Output=T>{#[inline]fn unit()->Self::T{Zero::zero()}}impl<T>Associative for AdditiveOperation<T>where T:Clone+Zero+Add<Output=T>{}impl<T>Commutative for AdditiveOperation<T>where T:Clone+Zero+Add<Output=T>{}impl<T>Invertible for AdditiveOperation<T>where T:Clone+Zero+Add<Output=T>+Sub<Output=T>+Neg<Output=T>{#[inline]fn inverse(x:&Self::T)->Self::T{-x.clone()}#[inline]fn rinv_operate(x:&Self::T,y:&Self::T)->Self::T{x.clone()-y.clone()}}}
// codesnip-guard: Graph
#[cfg_attr(any(),rustfmt::skip)]pub use self::graph_base::*;#[cfg_attr(any(),rustfmt::skip)]mod graph_base{#[doc=" A neighboring vertex and the label of the arc used to reach it."]#[derive(Debug,Clone,Copy,PartialEq,Eq,PartialOrd,Ord,Hash)]pub struct Neighbor<V,L>{pub to:V,pub label:L}impl<V,L>Neighbor<V,L>{#[inline]pub fn new(to:V,label:L)->Self{Self{to,label}}}impl<V,L>From<(V,L)>for Neighbor<V,L>{#[inline]fn from((to,label):(V,L))->Self{Self::new(to,label)}}#[doc=" A finite graph whose outgoing arcs can be iterated without allocation."]pub trait Graph{type Vertex:Copy+Eq;type Label;type Vertices<'g>:Iterator<Item=Self::Vertex>where Self:'g;type Neighbors<'g>:Iterator<Item=Neighbor<Self::Vertex,Self::Label>>where Self:'g;fn vsize(&self)->usize;fn vertices(&self)->Self::Vertices<'_>;fn neighbors(&self,vertex:Self::Vertex)->Self::Neighbors<'_>;}#[doc=" A graph whose adjacency relation represents directed arcs."]pub trait DirectedGraph:Graph{}pub trait VertexMap<T>:Graph{type Vmap;fn construct_vmap<F>(&self,f:F)->Self::Vmap where F:FnMut()->T;fn vmap_get<'a>(&self,map:&'a Self::Vmap,vertex:Self::Vertex)->&'a T;fn vmap_get_mut<'a>(&self,map:&'a mut Self::Vmap,vertex:Self::Vertex)->&'a mut T;#[inline]fn vmap_set(&self,map:&mut Self::Vmap,vertex:Self::Vertex,value:T){*self.vmap_get_mut(map,vertex)=value;}}pub trait EdgeMap<T>:Graph{type Emap;fn construct_emap<F>(&self,f:F)->Self::Emap where F:FnMut()->T;fn emap_get<'a>(&self,map:&'a Self::Emap,eid:Self::Label)->&'a T;fn emap_get_mut<'a>(&self,map:&'a mut Self::Emap,eid:Self::Label)->&'a mut T;#[inline]fn emap_set(&self,map:&mut Self::Emap,eid:Self::Label,value:T){*self.emap_get_mut(map,eid)=value;}}}
// codesnip-guard: MultiplicativeOperation
#[cfg_attr(any(),rustfmt::skip)]pub use self::multiplicative_operation_impl::MultiplicativeOperation;#[cfg_attr(any(),rustfmt::skip)]mod multiplicative_operation_impl{use super::*;use std::{marker::PhantomData,ops::{Div,Mul}};#[doc=" $\\times$"]pub struct MultiplicativeOperation<T>where T:Clone+One+Mul<Output=T>{_marker:PhantomData<fn()->T>}impl<T>Magma for MultiplicativeOperation<T>where T:Clone+One+Mul<Output=T>{type T=T;#[inline]fn operate(x:&Self::T,y:&Self::T)->Self::T{x.clone()*y.clone()}}impl<T>Unital for MultiplicativeOperation<T>where T:Clone+One+Mul<Output=T>{#[inline]fn unit()->Self::T{One::one()}}impl<T>Associative for MultiplicativeOperation<T>where T:Clone+One+Mul<Output=T>{}impl<T>Commutative for MultiplicativeOperation<T>where T:Clone+One+Mul<Output=T>{}impl<T>Invertible for MultiplicativeOperation<T>where T:Clone+One+Mul<Output=T>+Div<Output=T>{#[inline]fn inverse(x:&Self::T)->Self::T{Self::unit().div(x.clone())}#[inline]fn rinv_operate(x:&Self::T,y:&Self::T)->Self::T{(x.clone()).div(y.clone())}}}
// codesnip-guard: PartialIgnoredOrd
#[cfg_attr(any(),rustfmt::skip)]pub use self::partial_ignored_ord::PartialIgnoredOrd;#[cfg_attr(any(),rustfmt::skip)]mod partial_ignored_ord{#[derive(Debug,Default,Clone,Copy)]pub struct PartialIgnoredOrd<T,U>(pub T,pub U);impl<T:Eq,U>Eq for PartialIgnoredOrd<T,U>{}impl<T,U>PartialEq for PartialIgnoredOrd<T,U>where T:PartialEq{fn eq(&self,other:&Self)->bool{self.0 .eq(&other.0)}}impl<T,U>PartialOrd for PartialIgnoredOrd<T,U>where T:PartialOrd{fn partial_cmp(&self,other:&Self)->Option<std::cmp::Ordering>{self.0 .partial_cmp(&other.0)}}impl<T,U>Ord for PartialIgnoredOrd<T,U>where T:Ord{fn cmp(&self,other:&Self)->std::cmp::Ordering{self.0 .cmp(&other.0)}}}
// 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: bounded
#[cfg_attr(any(),rustfmt::skip)]pub use self::bounded::Bounded;#[cfg_attr(any(),rustfmt::skip)]mod bounded{#[doc=" Trait for max/min bounds"]pub trait Bounded:Sized+PartialOrd{fn maximum()->Self;fn minimum()->Self;fn is_maximum(&self)->bool{self==&Self::maximum()}fn is_minimum(&self)->bool{self==&Self::minimum()}fn set_maximum(&mut self){*self=Self::maximum()}fn set_minimum(&mut self){*self=Self::minimum()}}macro_rules!impl_bounded_num{($($t:ident)*)=>{$(impl Bounded for$t{fn maximum()->Self{$t::MAX}fn minimum()->Self{$t::MIN}})*};}impl_bounded_num!(u8 u16 u32 u64 u128 usize i8 i16 i32 i64 i128 isize f32 f64);macro_rules!impl_bounded_tuple{(@impl$($T:ident)*)=>{impl<$($T:Bounded),*>Bounded for($($T,)*){fn maximum()->Self{($(<$T as Bounded>::maximum(),)*)}fn minimum()->Self{($(<$T as Bounded>::minimum(),)*)}}};(@inner$($T:ident)*,)=>{impl_bounded_tuple!(@impl$($T)*);};(@inner$($T:ident)*,$U:ident$($Rest:ident)*)=>{impl_bounded_tuple!(@impl$($T)*);impl_bounded_tuple!(@inner$($T)*$U,$($Rest)*);};($T:ident$($Rest:ident)*)=>{impl_bounded_tuple!(@inner$T,$($Rest)*);};}impl_bounded_tuple!(A B C D E F G H I J);impl Bounded for(){fn maximum()->Self{}fn minimum()->Self{}}impl Bounded for bool{fn maximum()->Self{true}fn minimum()->Self{false}}impl<T>Bounded for Option<T>where T:Bounded{fn maximum()->Self{Some(<T as Bounded>::maximum())}fn minimum()->Self{None}}impl<T>Bounded for std::cmp::Reverse<T>where T:Bounded{fn maximum()->Self{std::cmp::Reverse(<T as Bounded>::minimum())}fn minimum()->Self{std::cmp::Reverse(<T as Bounded>::maximum())}}}
// codesnip-guard: ring
#[cfg_attr(any(),rustfmt::skip)]pub use self::ring::*;#[cfg_attr(any(),rustfmt::skip)]mod ring{use super::*;use std::{marker::PhantomData,num::Wrapping,ops::{Add,Mul}};pub trait SemiRing{type T:Clone;type Additive:AbelianMonoid<T=Self::T>;type Multiplicative:Monoid<T=Self::T>;#[doc=" additive identity: $0$"]fn zero()->Self::T{<Self::Additive as Unital>::unit()}fn is_zero(x:&Self::T)->bool where Self::T:PartialEq{*x==Self::zero()}#[doc=" multiplicative identity: $1$"]fn one()->Self::T{<Self::Multiplicative as Unital>::unit()}fn is_one(x:&Self::T)->bool where Self::T:PartialEq{*x==Self::one()}#[doc=" additive operaion: $+$"]fn add(x:&Self::T,y:&Self::T)->Self::T{<Self::Additive as Magma>::operate(x,y)}#[doc=" multiplicative operaion: $+$"]fn mul(x:&Self::T,y:&Self::T)->Self::T{<Self::Multiplicative as Magma>::operate(x,y)}fn try_matrix_product(_a:&[Vec<Self::T>],_b:&[Vec<Self::T>])->Option<Vec<Vec<Self::T>>>{None}fn dot_product(x:&[Self::T],y:&[Self::T])->Self::T{assert_eq!(x.len(),y.len());x.iter().zip(y).fold(Self::zero(),|mut sum,(x,y)|{Self::add_assign(&mut sum,&Self::mul(x,y));sum})}fn add_scaled_assign(x:&mut[Self::T],y:&[Self::T],a:&Self::T){assert_eq!(x.len(),y.len());for(x,y)in x.iter_mut().zip(y){Self::add_assign(x,&Self::mul(a,y));}}fn add_assign(x:&mut Self::T,y:&Self::T){<Self::Additive as Magma>::operate_assign(x,y);}fn mul_assign(x:&mut Self::T,y:&Self::T){<Self::Multiplicative as Magma>::operate_assign(x,y);}}pub trait Ring:SemiRing<Additive:Invertible>{#[doc=" additive inverse: $-$"]fn neg(x:&Self::T)->Self::T{<Self::Additive as Invertible>::inverse(x)}#[doc=" additive right inversed operaion: $-$"]fn sub(x:&Self::T,y:&Self::T)->Self::T{<Self::Additive as Invertible>::rinv_operate(x,y)}fn sub_assign(x:&mut Self::T,y:&Self::T){<Self::Additive as Invertible>::rinv_operate_assign(x,y);}}impl<R>Ring for R where R:SemiRing<Additive:Invertible>{}pub trait Field:Ring<Multiplicative:Invertible>{#[doc=" multiplicative inverse: $-$"]fn inv(x:&Self::T)->Self::T{<Self::Multiplicative as Invertible>::inverse(x)}#[doc=" multiplicative right inversed operaion: $-$"]fn div(x:&Self::T,y:&Self::T)->Self::T{<Self::Multiplicative as Invertible>::rinv_operate(x,y)}fn div_assign(x:&mut Self::T,y:&Self::T){<Self::Multiplicative as Invertible>::rinv_operate_assign(x,y);}}impl<F>Field for F where F:Ring<Multiplicative:Invertible>{}pub trait DotProduct:Sized+Clone+Zero+Add<Output=Self>+Mul<Output=Self>{fn try_matrix_product(_a:&[Vec<Self>],_b:&[Vec<Self>])->Option<Vec<Vec<Self>>>{None}fn add_scaled_assign(x:&mut[Self],y:&[Self],a:&Self){assert_eq!(x.len(),y.len());for(x,y)in x.iter_mut().zip(y){*x=x.clone()+a.clone()*y.clone();}}fn dot_product(x:&[Self],y:&[Self])->Self{assert_eq!(x.len(),y.len());x.iter().zip(y).fold(Self::zero(),|sum,(x,y)|sum+x.clone()*y.clone())}}macro_rules!impl_dot_product{($($t:ty)*)=>{$(impl DotProduct for$t{})*};}impl_dot_product!(u8 u16 u32 u64 usize u128 i8 i16 i32 i64 isize i128 f32 f64);impl<T>DotProduct for Wrapping<T>where Wrapping<T>:Clone+Zero+Add<Output=Wrapping<T>>+Mul<Output=Wrapping<T>>{}#[doc=" $+,\\times$"]pub struct AddMulOperation<T>where T:DotProduct+One{_marker:PhantomData<fn()->T>}impl<T>SemiRing for AddMulOperation<T>where T:DotProduct+One{type T=T;type Additive=AdditiveOperation<T>;type Multiplicative=MultiplicativeOperation<T>;#[inline]fn try_matrix_product(a:&[Vec<T>],b:&[Vec<T>])->Option<Vec<Vec<T>>>{T::try_matrix_product(a,b)}#[inline]fn dot_product(x:&[Self::T],y:&[Self::T])->Self::T{T::dot_product(x,y)}#[inline]fn add_scaled_assign(x:&mut[Self::T],y:&[Self::T],a:&Self::T){T::add_scaled_assign(x,y,a);}}}
// 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())});}