// codesnip-guard: prime_factors
#[cfg_attr(any(),rustfmt::skip)]pub use self::prime_factors::{divisors,prime_factors,prime_factors_flatten};#[cfg_attr(any(),rustfmt::skip)]mod prime_factors{use super::{BarrettReduction,Xorshift,gcd,miller_rabin_with_br};struct MontgomeryReduction64{modulus:u64,inverse:u64}impl MontgomeryReduction64{fn new(modulus:u64)->Self{let mut inverse=modulus;for _ in 0..6{inverse=inverse.wrapping_mul(2u64.wrapping_sub(modulus.wrapping_mul(inverse)));}Self{modulus,inverse}}fn sub(&self,lhs:u64,rhs:u64)->u64{let(value,borrow)=lhs.overflowing_sub(rhs);value.wrapping_add((borrow as u64).wrapping_neg()&self.modulus)}fn mul(&self,lhs:u64,rhs:u64)->u64{let product=lhs as u128*rhs as u128;let(value,borrow)=((product>>64)as u64).overflowing_sub((((product as u64).wrapping_mul(self.inverse)as u128*self.modulus as u128)>>64)as u64);value.wrapping_add((borrow as u64).wrapping_neg()&self.modulus)}}fn find_factor(n:u64)->Option<u64>{let br=BarrettReduction::<u128>::new(n as u128);if miller_rabin_with_br(n,&br){return None;}let mr=MontgomeryReduction64::new(n);let mut rng=Xorshift::default();let(mut y0,mut c)=(0,n-1);loop{let(mut x,mut y,mut ys,mut g,mut q,mut r,mut k)=(0,y0,0,1,1,1,0);while g==1&&r<=1<<20{x=y;while k<r&&g==1{ys=y;for _ in 0..1024 .min(r-k){y=mr.sub(mr.mul(y,y),c);q=mr.mul(q,mr.sub(x,y));}g=gcd(q,n);k+=1024;}k=r;r<<=1;}if g==n{g=1;y=ys;while g==1{y=mr.sub(mr.mul(y,y),c);g=gcd(mr.sub(x,y),n);}}if g!=1&&g!=n{return Some(g);}y0=((rng.rand64()as u128*(n-2)as u128)>>64)as u64+2;c=((rng.rand64()as u128*(n-1)as u128)>>64)as u64+1;}}pub fn prime_factors_flatten(mut n:u64)->Vec<u64>{if n==0{return vec![];}let k=n.trailing_zeros();let mut res=vec![2;k as usize];n>>=k;while n.is_multiple_of(3){res.push(3);n/=3;}if n!=1{let mut c=vec![n];while let Some(n)=c.pop(){if let Some(m)=find_factor(n){c.push(m);c.push(n/m);}else{res.push(n);}}}res.sort_unstable();res}pub fn prime_factors(n:u64)->Vec<(u64,u32)>{let mut res=Vec::new();for a in prime_factors_flatten(n){if let Some((p,len))=res.last_mut()&&p==&a{*len+=1;continue;}res.push((a,1));}res}pub fn divisors(n:u64)->Vec<u64>{let mut d=vec![1u64];for(p,c)in prime_factors(n){let k=d.len();let mut acc=1;for _ in 0..c{acc*=p;for i in 0..k{d.push(d[i]*acc);}}}d.sort_unstable();d}}
// codesnip-guard: BarrettReduction
#[cfg_attr(any(),rustfmt::skip)]pub use self::barrett_reduction::{BarrettReduction,Barrettable};#[cfg_attr(any(),rustfmt::skip)]mod barrett_reduction{use super::{One,Zero};use std::ops::{Add,Mul,Sub};#[derive(Debug,Clone,Copy)]pub struct BarrettReduction<T>{m:T,im:T}impl<T>BarrettReduction<T>where T:Barrettable{pub fn new(m:T)->Self{Self{m,im:T::inv_mod_approx(m)}}pub const fn new_with_im(m:T,im:T)->Self{Self{m,im}}pub const fn get_mod(&self)->T{self.m}pub fn div_rem(&self,a:T)->(T,T){T::barrett_reduce(a,self.m,self.im)}pub fn div(&self,a:T)->T{self.div_rem(a).0}pub fn rem(&self,a:T)->T{self.div_rem(a).1}}pub trait Barrettable:Sized+Copy+PartialOrd+Zero+One+Add<Output=Self>+Sub<Output=Self>+Mul<Output=Self>{fn inv_mod_approx(m:Self)->Self;fn div_approx(self,im:Self)->Self;fn barrett_reduce(self,m:Self,im:Self)->(Self,Self){if m==Self::one(){return(self,Self::zero());}let q=self.div_approx(im);let r=self-q*m;if m<=r{(q+Self::one(),r-m)}else{(q,r)}}}impl Barrettable for u32{fn inv_mod_approx(m:Self)->Self{!0/m}fn div_approx(self,im:Self)->Self{((self as u64*im as u64)>>32)as u32}}impl Barrettable for u64{fn inv_mod_approx(m:Self)->Self{!0/m}fn div_approx(self,im:Self)->Self{((self as u128*im as u128)>>64)as u64}}impl Barrettable for u128{fn inv_mod_approx(m:Self)->Self{!0/m}fn div_approx(self,im:Self)->Self{const MASK64:u128=0xffff_ffff_ffff_ffff;let au=self>>64;let ad=self&MASK64;let imu=im>>64;let imd=im&MASK64;let res=au*imu;let x=((ad*imd)>>64)+au*imd;let(x,c)=x.overflowing_add(ad*imu);res+((c as u128)<<64)+(x>>64)}}}
// 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: gcd
#[cfg_attr(any(),rustfmt::skip)]#[doc=" binary gcd"]pub fn gcd(mut a:u64,mut b:u64)->u64{if a==0{return b;}if b==0{return a;}let u=a.trailing_zeros();let v=b.trailing_zeros();a>>=u;b>>=v;let k=std::cmp::min(u,v);while a!=b{if a<b{std::mem::swap(&mut a,&mut b);}a-=b;a>>=a.trailing_zeros();}a<<k}
// codesnip-guard: miller_rabin
#[cfg_attr(any(),rustfmt::skip)]pub use self::miller_rabin::{miller_rabin,miller_rabin_with_br};#[cfg_attr(any(),rustfmt::skip)]mod miller_rabin{use super::BarrettReduction;macro_rules!impl_test_mr{($name:ident,$ty:ty,$upty:ty)=>{fn$name(n:$ty,br:&BarrettReduction<$upty>,a:$ty)->bool{if br.rem(a as$upty)==0{return true;}let d=n-1;let k=d.trailing_zeros();let mut d=d>>k;let mut y={let mut a=a as$upty;let mut y:$upty=1;while d>0{if d&1==1{y=br.rem(y*a);}a=br.rem(a*a);d>>=1;}y as$ty};if y==1||y==n-1{true}else{for _ in 0..k-1{y=br.rem(y as$upty*y as$upty)as$ty;if y==n-1{return true;}}false}}};}impl_test_mr!(test_mr32,u32,u64);impl_test_mr!(test_mr64,u64,u128);#[doc=" <http://miller-rabin.appspot.com/>"]macro_rules!impl_mr{($name:ident,$test:ident,$ty:ty,$upty:ty,[$($th:expr,[$($a:expr),+]),+],|$n:ident,$br:ident|$last:expr)=>{fn$name($n:$ty,$br:&BarrettReduction<$upty>)->bool{$(if$n>=$th{return$($test($n,$br,$a))&&+})+$last}};}impl_mr!(mr32,test_mr32,u32,u64,[316349281,[2,7,61],49141,[11000544,31481107]],|n,br|test_mr32(n,br,921211727));impl_mr!(mr64,test_mr64,u64,u128,[585226005592931977,[2,325,9375,28178,450775,9780504,1795265022],7999252175582851,[2,123635709730000,9233062284813009,43835965440333360,761179012939631437,1263739024124850375],55245642489451,[2,4130806001517,149795463772692060,186635894390467037,3967304179347715805],350269456337,[2,141889084524735,1199124725622454117,11096072698276303650],1050535501,[4230279247111683200,14694767155120705706,16641139526367750375]],|n,br|mr32(n as u32,&BarrettReduction::<u64>::new(n)));pub fn miller_rabin_with_br(n:u64,br:&BarrettReduction<u128>)->bool{if n.is_multiple_of(2){return n==2;}if n.is_multiple_of(3){return n==3;}if n.is_multiple_of(5){return n==5;}if n.is_multiple_of(7){return n==7;}if n<121{n>2}else{mr64(n,br)}}pub fn miller_rabin(n:u64)->bool{n>=2&&miller_rabin_with_br(n,&BarrettReduction::<u128>::new(n as u128))}}
// 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())});}