// codesnip-guard: RollingHash
#[cfg_attr(any(),rustfmt::skip)]pub use self::rolling_hash::{Gf2_63x1,Gf2_63x2,Gf2_63x3,HashedRangeChained,Mersenne61x1,Mersenne61x2,Mersenne61x3,RollingHasher};#[cfg_attr(any(),rustfmt::skip)]pub mod rolling_hash{use super::{Gf2_63,Invertible,Mersenne61,Monoid,Ring,SemiRing,Xorshift};use std::{cmp::Ordering,fmt::{self,Debug},marker::PhantomData,ops::{Bound,RangeBounds,RangeInclusive}};pub trait RollingHasher{type T;type Hash:Copy+Eq;fn init_with_rng(len:usize,rng:&mut Xorshift);fn init(len:usize){let mut rng=Xorshift::new();Self::init_with_rng(len,&mut rng);}fn ensure(len:usize);fn hash_sequence<I>(iter:I)->HashedSequence<Self>where I:IntoIterator<Item=Self::T>;fn hash_substr(hashed:&[Self::Hash])->Hashed<Self>;fn concat_hash(x:&Hashed<Self>,y:&Hashed<Self>)->Hashed<Self>;fn empty_hash()->Hashed<Self>;}#[derive(Debug)]pub struct HashedSequence<Hasher>where Hasher:RollingHasher+?Sized{hashed:Vec<Hasher::Hash>,_marker:PhantomData<fn()->Hasher>}impl<Hasher>HashedSequence<Hasher>where Hasher:RollingHasher+?Sized{fn new(hashed:Vec<Hasher::Hash>)->Self{Self{hashed,_marker:PhantomData}}pub fn len(&self)->usize{self.hashed.len()-1}pub fn is_empty(&self)->bool{self.len()==0}pub fn range<R>(&self,range:R)->HashedRange<'_,Hasher>where R:RangeBounds<usize>{HashedRange::new(&self.hashed[to_range(range,self.len())])}pub fn hash_range<R>(&self,range:R)->Hashed<Hasher>where R:RangeBounds<usize>{self.range(range).hash()}}#[derive(Debug)]pub struct HashedRange<'a,Hasher>where Hasher:RollingHasher+?Sized{hashed:&'a[Hasher::Hash],_marker:PhantomData<fn()->Hasher>}impl<Hasher>Clone for HashedRange<'_,Hasher>where Hasher:RollingHasher+?Sized{fn clone(&self)->Self{*self}}impl<Hasher>Copy for HashedRange<'_,Hasher>where Hasher:RollingHasher+?Sized{}impl<Hasher>PartialEq for HashedRange<'_,Hasher>where Hasher:RollingHasher+?Sized{fn eq(&self,other:&Self)->bool{self.hash()==other.hash()}}impl<Hasher>Eq for HashedRange<'_,Hasher>where Hasher:RollingHasher+?Sized{}impl<Hasher>PartialOrd for HashedRange<'_,Hasher>where Hasher:RollingHasher<Hash:PartialOrd>+?Sized{fn partial_cmp(&self,other:&Self)->Option<Ordering>{let n=self.longest_common_prefix(other);match(self.len()>n,other.len()>n){(true,true)=>{let x=self.hash_range(n..=n);let y=other.hash_range(n..=n);x.hash.partial_cmp(&y.hash)}(x,y)=>Some(x.cmp(&y)),}}}impl<Hasher>Ord for HashedRange<'_,Hasher>where Hasher:RollingHasher<Hash:Ord>+?Sized{fn cmp(&self,other:&Self)->Ordering{let n=self.longest_common_prefix(other);match(self.len()>n,other.len()>n){(true,true)=>{let x=self.hash_range(n..=n);let y=other.hash_range(n..=n);x.hash.cmp(&y.hash)}(x,y)=>x.cmp(&y),}}}impl<'a,Hasher>HashedRange<'a,Hasher>where Hasher:RollingHasher+?Sized{fn new(hashed:&'a[Hasher::Hash])->Self{Self{hashed,_marker:PhantomData}}pub fn len(&self)->usize{self.hashed.len()-1}pub fn is_empty(&self)->bool{self.len()==0}pub fn range<R>(&self,range:R)->HashedRange<'a,Hasher>where R:RangeBounds<usize>{HashedRange::new(&self.hashed[to_range(range,self.len())])}pub fn hash_range<R>(&self,range:R)->Hashed<Hasher>where R:RangeBounds<usize>{self.range(range).hash()}pub fn hash(&self)->Hashed<Hasher>{Hasher::hash_substr(self.hashed)}pub fn longest_common_prefix(&self,other:&Self)->usize{let n=self.len().min(other.len());let mut ok=0usize;let mut err=n+1;while ok+1<err{let mid=ok.midpoint(err);if self.range(..mid).hash()==other.range(..mid).hash(){ok=mid;}else{err=mid;}}ok}pub fn chainable(self)->HashedRangeChained<'a,Hasher>{vec![self].into()}}pub struct HashedRangeChained<'a,Hasher>where Hasher:RollingHasher+?Sized{chained:Vec<HashedRange<'a,Hasher>>,_marker:PhantomData<fn()->Hasher>}impl<Hasher:Debug>Debug for HashedRangeChained<'_,Hasher>where Hasher:RollingHasher<Hash:Debug>+?Sized{fn fmt(&self,f:&mut fmt::Formatter<'_>)->fmt::Result{f.debug_struct("HashedRangeChained").field("chained",&self.chained).finish()}}impl<Hasher:Default>Default for HashedRangeChained<'_,Hasher>where Hasher:RollingHasher{fn default()->Self{Self{chained:Default::default(),_marker:Default::default()}}}impl<Hasher:Clone>Clone for HashedRangeChained<'_,Hasher>where Hasher:RollingHasher{fn clone(&self)->Self{Self{chained:self.chained.clone(),_marker:self._marker}}}impl<Hasher>PartialEq for HashedRangeChained<'_,Hasher>where Hasher:RollingHasher+?Sized{fn eq(&self,other:&Self)->bool{let mut a=self.chained.iter().cloned();let mut b=other.chained.iter().cloned();macro_rules!next{($iter:expr)=>{loop{if let Some(x)=$iter.next(){if x.len()>0{break Some(x);}}else{break None;}}};}let mut x:Option<HashedRange<'_,Hasher>>=None;let mut y:Option<HashedRange<'_,Hasher>>=None;loop{if x.is_none_or(|x|x.is_empty()){x=next!(a);}if y.is_none_or(|y|y.is_empty()){y=next!(b);}if let(Some(x),Some(y))=(&mut x,&mut y){let k=x.len().min(y.len());if x.range(..k)!=y.range(..k){return false;}*x=x.range(k..);*y=y.range(k..);}else{break x.is_none()==y.is_none();}}}}impl<Hasher>Eq for HashedRangeChained<'_,Hasher>where Hasher:RollingHasher+?Sized{}impl<Hasher>PartialOrd for HashedRangeChained<'_,Hasher>where Hasher:RollingHasher<Hash:PartialOrd>+?Sized{fn partial_cmp(&self,other:&Self)->Option<Ordering>{let mut a=self.chained.iter().cloned();let mut b=other.chained.iter().cloned();macro_rules!next{($iter:expr)=>{loop{if let Some(x)=$iter.next(){if x.len()>0{break Some(x);}}else{break None;}}};}let mut x:Option<HashedRange<'_,Hasher>>=None;let mut y:Option<HashedRange<'_,Hasher>>=None;loop{if x.is_none_or(|x|x.is_empty()){x=next!(a);}if y.is_none_or(|y|y.is_empty()){y=next!(b);}if let(Some(x),Some(y))=(&mut x,&mut y){let k=x.longest_common_prefix(y);if x.len()>k&&y.len()>k{let x=x.hash_range(k..=k);let y=y.hash_range(k..=k);break x.hash.partial_cmp(&y.hash);};*x=x.range(k..);*y=y.range(k..);}else{break x.is_some().partial_cmp(&y.is_some());}}}}impl<Hasher>Ord for HashedRangeChained<'_,Hasher>where Hasher:RollingHasher<Hash:Ord>+?Sized{fn cmp(&self,other:&Self)->Ordering{let mut a=self.chained.iter().cloned();let mut b=other.chained.iter().cloned();macro_rules!next{($iter:expr)=>{loop{if let Some(x)=$iter.next(){if x.len()>0{break Some(x);}}else{break None;}}};}let mut x:Option<HashedRange<'_,Hasher>>=None;let mut y:Option<HashedRange<'_,Hasher>>=None;loop{if x.is_none_or(|x|x.is_empty()){x=next!(a);}if y.is_none_or(|y|y.is_empty()){y=next!(b);}if let(Some(x),Some(y))=(&mut x,&mut y){let k=x.longest_common_prefix(y);if x.len()>k&&y.len()>k{let x=x.hash_range(k..=k);let y=y.hash_range(k..=k);break x.hash.cmp(&y.hash);};*x=x.range(k..);*y=y.range(k..);}else{break x.is_some().cmp(&y.is_some());}}}}impl<'a,Hasher>From<Vec<HashedRange<'a,Hasher>>>for HashedRangeChained<'a,Hasher>where Hasher:RollingHasher+?Sized{fn from(hashed:Vec<HashedRange<'a,Hasher>>)->Self{Self{chained:hashed,_marker:PhantomData}}}impl<'a,Hasher>HashedRangeChained<'a,Hasher>where Hasher:RollingHasher+?Sized{pub fn chain(mut self,x:HashedRange<'a,Hasher>)->Self{self.chained.push(x);self}pub fn push(&mut self,x:HashedRange<'a,Hasher>){self.chained.push(x);}}fn to_range<R>(range:R,ub:usize)->RangeInclusive<usize>where R:RangeBounds<usize>{let l=match range.start_bound(){Bound::Included(l)=>*l,Bound::Excluded(l)=>l+1,Bound::Unbounded=>0,};let r=match range.end_bound(){Bound::Included(r)=>r+1,Bound::Excluded(r)=>*r,Bound::Unbounded=>ub,};l..=r}#[derive(Debug)]pub struct Hashed<Hasher>where Hasher:RollingHasher+?Sized{len:usize,hash:Hasher::Hash,_marker:PhantomData<fn()->Hasher>}impl<Hasher>std::hash::Hash for Hashed<Hasher>where Hasher:RollingHasher<Hash:std::hash::Hash>+?Sized{fn hash<H:std::hash::Hasher>(&self,state:&mut H){self.len.hash(state);self.hash.hash(state);self._marker.hash(state);}}impl<Hasher>Hashed<Hasher>where Hasher:RollingHasher+?Sized{fn new(len:usize,hash:Hasher::Hash)->Self{Self{len,hash,_marker:PhantomData}}pub fn concat(&self,other:&Self)->Self{Hasher::concat_hash(self,other)}pub fn pow(&self,n:usize)->Self{let mut res=Hasher::empty_hash();let mut x=*self;let mut n=n;while n>0{if n&1==1{res=res.concat(&x);}n>>=1;if n!=0{x=x.concat(&x);}}res}}impl<Hasher>Clone for Hashed<Hasher>where Hasher:RollingHasher+?Sized{fn clone(&self)->Self{*self}}impl<Hasher>Copy for Hashed<Hasher>where Hasher:RollingHasher+?Sized{}impl<Hasher>PartialEq for Hashed<Hasher>where Hasher:RollingHasher+?Sized{fn eq(&self,other:&Self)->bool{self.len==other.len&&self.hash==other.hash}}impl<Hasher>Eq for Hashed<Hasher>where Hasher:RollingHasher+?Sized{}#[derive(Debug)]struct RollingHashPrecalc<R>where R:SemiRing{base:R::T,pow:Vec<R::T>}impl<R>Default for RollingHashPrecalc<R>where R:SemiRing<T:Default>{fn default()->Self{Self{base:Default::default(),pow:Default::default()}}}impl<R>RollingHashPrecalc<R>where R:SemiRing<Additive:Invertible>{fn new(base:R::T)->Self{Self{base,pow:vec![R::one()]}}fn ensure_pow(&mut self,len:usize){if self.pow.len()<=len{self.pow.reserve(len-self.pow.len()+1);if self.pow.is_empty(){self.pow.push(R::one());}for _ in 0..=len-self.pow.len(){self.pow.push(R::mul(self.pow.last().unwrap(),&self.base));}}}fn mul1_add(&self,x:&R::T,y:&R::T)->R::T{R::add(&R::mul(x,&self.base),y)}fn muln_add(&mut self,x:&R::T,y:&R::T,n:usize)->R::T{if let Some(pow)=self.pow.get(n){R::add(&R::mul(x,pow),y)}else{let pow=<R::Multiplicative as Monoid>::pow(self.base.clone(),n);R::add(&R::mul(x,&pow),y)}}fn muln_sub(&mut self,l:&R::T,r:&R::T,n:usize)->R::T{if let Some(pow)=self.pow.get(n){R::sub(r,&R::mul(l,pow))}else{let pow=<R::Multiplicative as Monoid>::pow(self.base.clone(),n);R::sub(r,&R::mul(l,&pow))}}}macro_rules!impl_rolling_hasher{(@inner$T:ident,$R:ty,[$($i:tt)*][$($s:tt)*][$a:tt$($tt:tt)*][$k:tt$($j:tt)*])=>{impl_rolling_hasher!(@inner$T,$R,[$($i)*$k][$($s)*()][$($tt)*][$($j)*]);};(@inner$T:ident,$R:ty,[$($i:tt)+][$($s:tt)+][][$len:tt$($j:tt)*])=>{#[derive(Debug,Clone,Copy,Hash,PartialEq,Eq,PartialOrd,Ord)]pub enum$T{}impl$T{fn __rolling_hash_local_key()->&'static::std::thread::LocalKey<::std::cell::Cell<[RollingHashPrecalc<$R>;$len]>>{::std::thread_local!(static __LOCAL_KEY: ::std::cell::Cell<[RollingHashPrecalc<$R>;$len]> =::std::cell::Cell::new(Default::default()));&__LOCAL_KEY}}impl RollingHasher for$T{type T=<$R as SemiRing>::T;type Hash=[<$R as SemiRing>::T;$len];fn init_with_rng(len:usize,rng:&mut Xorshift){Self::__rolling_hash_local_key().with(|cell|{if unsafe{(&*cell.as_ptr()).iter().all(|p|p.base==0)}{cell.set([$({$s;RollingHashPrecalc::new(rng.rand(<$R>::MOD))},)+]);}});Self::ensure(len);}fn ensure(len:usize){Self::__rolling_hash_local_key().with(|cell|{unsafe{let arr=&mut*cell.as_ptr();$(arr[$i].ensure_pow(len);)+}})}fn hash_sequence<I>(iter:I)->HashedSequence<Self>where I:IntoIterator<Item=Self::T>,{let iter=iter.into_iter();let(lb,_)=iter.size_hint();let mut hashed=Vec::with_capacity(lb+1);hashed.push([$({$s;<$R>::zero()},)+]);unsafe{Self::__rolling_hash_local_key().with(|cell|{let arr=&*cell.as_ptr();for item in iter{let last=hashed.last().unwrap();let h=[$(arr[$i].mul1_add(&last[$i],&item),)+];hashed.push(h);}})};HashedSequence::new(hashed)}fn hash_substr(hashed:&[Self::Hash])->Hashed<Self>{let len=hashed.len()-1;let h=unsafe{Self::__rolling_hash_local_key().with(|cell|{let arr=&mut*cell.as_ptr();[$(arr[$i].muln_sub(&hashed[0][$i],&hashed[len][$i],len),)+]})};Hashed::new(len,h)}fn concat_hash(x:&Hashed<Self>,y:&Hashed<Self>)->Hashed<Self>{let len=y.len;let hash=unsafe{Self::__rolling_hash_local_key().with(|cell|{let arr=&mut*cell.as_ptr();[$(arr[$i].muln_add(&x.hash[$i],&y.hash[$i],len),)+]})};Hashed::new(x.len+y.len,hash)}fn empty_hash()->Hashed<Self>{Hashed::new(0,[$({$s;<$R>::zero()},)+])}}};($T:ident,$R:ty,[$($tt:tt)+])=>{impl_rolling_hasher!(@inner$T,$R,[][][$($tt)+][0 1 2 3 4 5 6 7 8 9]);};}impl_rolling_hasher!(Mersenne61x1,Mersenne61,[_]);impl_rolling_hasher!(Mersenne61x2,Mersenne61,[_ _]);impl_rolling_hasher!(Mersenne61x3,Mersenne61,[_ _ _]);impl_rolling_hasher!(Gf2_63x1,Gf2_63,[_]);impl_rolling_hasher!(Gf2_63x2,Gf2_63,[_ _]);impl_rolling_hasher!(Gf2_63x3,Gf2_63,[_ _ _]);}
// 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: BitXorOperation
#[cfg_attr(any(),rustfmt::skip)]pub use self::bitxor_operation_impl::{BitXorIdentity,BitXorOperation};#[cfg_attr(any(),rustfmt::skip)]mod bitxor_operation_impl{use super::*;use std::{marker::PhantomData,ops::BitXor};#[doc=" ^"]pub struct BitXorOperation<T>where T:Clone+BitXorIdentity{_marker:PhantomData<fn()->T>}pub trait BitXorIdentity:Sized+BitXor<Output=Self>{fn xor_zero()->Self;}#[macro_export]macro_rules!impl_bitxor_identity{([$($wh:tt)*],$t:ty,$xor_zero:expr)=>{impl<$($wh)*>BitXorIdentity for$t{#[inline]fn xor_zero()->Self{$xor_zero}}};($t:ty,$xor_zero:expr)=>{impl BitXorIdentity for$t{#[inline]fn xor_zero()->Self{$xor_zero}}};}impl_bitxor_identity!(bool,false);impl_bitxor_identity!(usize,0);impl_bitxor_identity!(u8,0);impl_bitxor_identity!(u16,0);impl_bitxor_identity!(u32,0);impl_bitxor_identity!(u64,0);impl_bitxor_identity!(u128,0);impl_bitxor_identity!(isize,0);impl_bitxor_identity!(i8,0);impl_bitxor_identity!(i16,0);impl_bitxor_identity!(i32,0);impl_bitxor_identity!(i64,0);impl_bitxor_identity!(i128,0);impl<T>Magma for BitXorOperation<T>where T:Clone+BitXorIdentity{type T=T;#[inline]fn operate(x:&Self::T,y:&Self::T)->Self::T{x.clone()^y.clone()}}impl<T>Unital for BitXorOperation<T>where T:Clone+BitXorIdentity{#[inline]fn unit()->Self::T{BitXorIdentity::xor_zero()}}impl<T>Associative for BitXorOperation<T>where T:Clone+BitXorIdentity{}impl<T>Commutative for BitXorOperation<T>where T:Clone+BitXorIdentity{}impl<T>Invertible for BitXorOperation<T>where T:Clone+BitXorIdentity{fn inverse(x:&Self::T)->Self::T{x.clone()}}}
// codesnip-guard: Gf2_63
#[cfg_attr(any(),rustfmt::skip)]pub use self::gf2_63::Gf2_63;#[cfg_attr(any(),rustfmt::skip)]mod gf2_63{use super::*;pub enum Gf2_63{}impl Gf2_63{pub const MOD:u64=1<<63;}impl Magma for Gf2_63{type T=u64;fn operate(x:&Self::T,y:&Self::T)->Self::T{#[cfg(target_arch="x86_64")]{use core::arch::x86_64::{_mm_clmulepi64_si128,_mm_extract_epi64,_mm_set_epi64x};unsafe{let a=_mm_set_epi64x(0,*x as i64);let b=_mm_set_epi64x(0,*y as i64);let c=_mm_clmulepi64_si128(a,b,0);let lo=_mm_extract_epi64(c,0)as u64;let hi=_mm_extract_epi64(c,1)as u64;let hi=(hi<<1)|(lo>>63);let lo=lo&!(!(0u64)<<63);lo^hi^(hi<<1)}}#[cfg(not(target_arch="x86_64"))]{let x=*x as u128;let mut bit=0u128;for i in 0u32..63{if y>>i&1!=0{bit^=x<<i;}}let hi=(bit>>64)as u64;let lo=(bit&((1<<64)-1))as u64;let hi=(hi<<1)|(lo>>63);let lo=lo&!(!(0u64)<<63);lo^hi^(hi<<1)}}}impl Unital for Gf2_63{fn unit()->Self::T{1}}impl Associative for Gf2_63{}impl Commutative for Gf2_63{}impl SemiRing for Gf2_63{type T=u64;type Additive=BitXorOperation<u64>;type Multiplicative=Self;}}
// codesnip-guard: Mersenne61
#[cfg_attr(any(),rustfmt::skip)]pub use self::mersenne61::Mersenne61;#[cfg_attr(any(),rustfmt::skip)]mod mersenne61{use super::*;pub enum Mersenne61Add{}impl Magma for Mersenne61Add{type T=u64;fn operate(x:&Self::T,y:&Self::T)->Self::T{let mut z=x+y;if z>=Mersenne61::MOD{z-=Mersenne61::MOD}z}}impl Unital for Mersenne61Add{fn unit()->Self::T{0}}impl Associative for Mersenne61Add{}impl Commutative for Mersenne61Add{}impl Invertible for Mersenne61Add{fn inverse(x:&Self::T)->Self::T{if*x==0{0}else{Mersenne61::MOD-x}}}pub enum Mersenne61{}impl Mersenne61{pub const MOD:u64=(1<<61)-1;}impl Magma for Mersenne61{type T=u64;fn operate(x:&Self::T,y:&Self::T)->Self::T{let z=*x as u128**y as u128;Mersenne61Add::operate(&((z>>61)as _),&(z as u64&Self::MOD))}}impl Unital for Mersenne61{fn unit()->Self::T{1}}impl Associative for Mersenne61{}impl Commutative for Mersenne61{}impl SemiRing for Mersenne61{type T=u64;type Additive=Mersenne61Add;type Multiplicative=Self;}}
// 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: Xorshift
#[cfg_attr(any(),rustfmt::skip)]pub use self::xorshift::Xorshift;#[cfg_attr(any(),rustfmt::skip)]mod xorshift{use std::{collections::hash_map::RandomState,hash::{BuildHasher,Hasher},iter::repeat_with};#[derive(Clone,Debug)]pub struct Xorshift{y:u64}impl Xorshift{pub fn new_with_seed(seed:u64)->Self{Xorshift{y:seed}}pub fn new()->Self{Xorshift::new_with_seed(RandomState::new().build_hasher().finish())}pub fn rand64(&mut self)->u64{self.y^=self.y<<5;self.y^=self.y>>17;self.y^=self.y<<11;self.y}pub fn rand(&mut self,k:u64)->u64{self.rand64()%k}pub fn rands(&mut self,k:u64,n:usize)->Vec<u64>{repeat_with(| |self.rand(k)).take(n).collect()}pub fn randf(&mut self)->f64{const UPPER_MASK:u64=0x3FF0_0000_0000_0000;const LOWER_MASK:u64=0x000F_FFFF_FFFF_FFFF;let x=self.rand64();let tmp=UPPER_MASK|(x&LOWER_MASK);let result:f64=f64::from_bits(tmp);f64::from_bits(f64::to_bits(result-1.0)^(x>>63))}pub fn gen_bool(&mut self,p:f64)->bool{self.randf()<p}pub fn shuffle<T>(&mut self,slice:&mut[T]){let mut n=slice.len();while n>1{let i=self.rand(n as _)as usize;n-=1;slice.swap(i,n);}}}impl Default for Xorshift{fn default()->Self{Xorshift::new_with_seed(0x2b99_2ddf_a232_49d6)}}}
// 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: 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())});}