#867384 (Rust) No.3030 ミラー・ラビン素数判定法のテスト

提出ソース
結果

問題	No.3030 ミラー・ラビン素数判定法のテスト
ユーザー	👑 Mizar
提出日時	2023-05-08 03:22:50
言語	Rust (1.77.0 + proconio)
結果	AC
実行時間	13 ms / 9,973 ms
コード長	62,832 bytes
コンパイル時間	17,498 ms
コンパイル使用メモリ	403,136 KB
実行使用メモリ	6,820 KB
最終ジャッジ日時	2024-11-25 00:13:55
合計ジャッジ時間	15,238 ms
ジャッジサーバーID （参考情報）	judge1 / judge2
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 6,816 KB
testcase_01	AC	1 ms 6,816 KB
testcase_02	AC	1 ms 6,820 KB
testcase_03	AC	1 ms 6,816 KB
testcase_04	AC	8 ms 6,816 KB
testcase_05	AC	9 ms 6,820 KB
testcase_06	AC	8 ms 6,820 KB
testcase_07	AC	8 ms 6,816 KB
testcase_08	AC	8 ms 6,820 KB
testcase_09	AC	13 ms 6,816 KB
権限があれば一括ダウンロードができます
ソースコード

raw source code
pub use __cargo_equip::prelude::*;

use crate::__cargo_equip::crates::{bpsw::*, input::*, invariant::*};
use std::io::prelude::*;

pub fn solve<I: NextToken>(input: &mut I) {
    // Initialize.
    #[rustfmt::skip] #[cfg(tcheck)] let tins = std::time::Instant::now();
    #[rustfmt::skip] #[cfg(tcheck)] let mut durs = Vec::with_capacity(16);
    #[rustfmt::skip] #[allow(unused_macros)] macro_rules! input {($($r:tt)*)=>{input_inner!{input,$($r)*}};}
    #[rustfmt::skip] #[allow(unused_macros)] macro_rules! read {($t:tt)=>{{read_value!(input,$t)}};}
    let mut obuf = Vec::<u8>::with_capacity(1 << 26);
    let mut out = std::io::stdout();

    input! { n: u32 }
    for i in 0..n {
        input! { xt: BytesToken }
        invariant!(obuf.len() + xt.as_slice().len() < obuf.capacity());
        obuf.extend_from_slice(xt.as_slice());
        let x = xt.as_slice().parse_u64_raw();
        let isprime = primetest_u64_bpsw(x);
        invariant!(obuf.len() + 3 < obuf.capacity());
        obuf.extend_from_slice(if isprime { b" 1\n" } else { b" 0\n" });
        if (i & 511) == 0 {
            out.write_all(&mut obuf).ok();
            obuf.clear();
        }
    }

    #[rustfmt::skip] #[cfg(tcheck)] durs.push((tins.elapsed(), "solve"));
    out.write_all(&mut obuf).ok();
    #[rustfmt::skip] #[cfg(tcheck)] durs.push((tins.elapsed(), "output"));

    // Execution Time.
    #[rustfmt::skip] #[cfg(tcheck)] for (dur, s) in durs.iter() { eprintln!("{:.6} {}", dur.as_secs_f64(), s); };
}

#[cfg(not(target_os = "linux"))]
fn launch() {
    let stdin = std::io::stdin();
    solve(&mut fastproconio::ProconIBufIter::new(stdin.lock()));
}
#[cfg(target_os = "linux")]
fn launch() {
    unsafe {
        use std::os::unix::io::FromRawFd;
        match std::fs::File::from_raw_fd(0).metadata() {
            Ok(metadata) if metadata.is_file() => {
                let filelen = metadata.len();
                let input = mmap(std::ptr::null_mut(), filelen as usize, 1, 2, 0, 0);
                solve(&mut BytesIter(std::slice::from_raw_parts(
                    input,
                    filelen as usize,
                )));
            }
            _ => {
                let stdin = std::io::stdin();
                solve(&mut ProconIBufIter::new(stdin.lock()));
            }
        }
    }
}

fn main() {
    const USE_THREAD: bool = false;
    if USE_THREAD {
        // In order to avoid potential stack overflow, spawn a new thread.
        let stack_size = 134_217_728; // 128 MB
        let thd = std::thread::Builder::new().stack_size(stack_size);
        thd.spawn(|| launch()).unwrap().join().unwrap();
    } else {
        launch()
    }
}

// The following code was expanded by `cargo-equip`.

///  # Bundled libraries
/// 
///  - `mizar-competitive-integer-issq 0.0.0 (path+██████████████████████████████████████████████████████████████████████████)`                       published in **missing** licensed under **missing** as `crate::__cargo_equip::crates::issq`
///  - `mizar-competitive-integer-jacobi 0.0.0 (path+████████████████████████████████████████████████████████████████████████████)`                   published in **missing** licensed under **missing** as `crate::__cargo_equip::crates::jacobi`
///  - `mizar-competitive-integer-modint32dynamic 0.0.0 (path+█████████████████████████████████████████████████████████████████████████████████████)` published in **missing** licensed under **missing** as `crate::__cargo_equip::crates::modint32dynamic`
///  - `mizar-competitive-integer-montodd 0.0.0 (path+█████████████████████████████████████████████████████████████████████████████)`                 published in **missing** licensed under **missing** as `crate::__cargo_equip::crates::montodd`
///  - `mizar-competitive-integer-sqrt 0.0.0 (path+██████████████████████████████████████████████████████████████████████████)`                       published in **missing** licensed under **missing** as `crate::__cargo_equip::crates::sqrt`
///  - `mizar-competitive-io-input 0.0.0 (path+██████████████████████████████████████████████████████████████████████)`                               published in **missing** licensed under **missing** as `crate::__cargo_equip::crates::input`
///  - `mizar-competitive-misc-invariant 0.0.0 (path+████████████████████████████████████████████████████████████████████████████)`                   published in **missing** licensed under **missing** as `crate::__cargo_equip::crates::invariant`
///  - `mizar-competitive-misc-primint 0.0.0 (path+██████████████████████████████████████████████████████████████████████████)`                       published in **missing** licensed under **missing** as `crate::__cargo_equip::crates::primint`
///  - `mizar-competitive-prime-bpsw 0.0.0 (path+████████████████████████████████████████████████████████████████████████)`                           published in **missing** licensed under **missing** as `crate::__cargo_equip::crates::bpsw`
#[cfg_attr(any(), rustfmt::skip)]
#[allow(unused)]
mod __cargo_equip {
    pub(crate) mod crates {
        pub mod issq {use crate::__cargo_equip::preludes::issq::*;use crate::__cargo_equip::crates::sqrt::sqrt_floor;macro_rules!fn_isqrt_n{($sqrt_newton:ident,$sqrt_exact:ident,$issq_newton:ident,$issq_mod32:ident,$issq_mod48:ident,$issq_mod3960:ident,$issq_mod4095:ident,$issq:ident,$x:ty,$w:literal)=>{pub fn$issq_mod32(x:$x)->bool{(0x02030213u32>>((x as u32)&31))&1==1}pub fn$issq_mod48(x:$x)->bool{(0x1202010213u64>>(x%48))&1==1}pub fn$issq_mod4095(x:$x)->bool{const SQTABLE_MOD4095:[u64;64]=[0x2001002010213,0x4200001008028001,0x20000010004,0x80200082010,0x1800008200044029,0x120080000010,0x2200000080410400,0x8100041000200800,0x800004000020100,0x402000400082201,0x9004000040,0x800002000880,0x18002000012000,0x801208,0x26100000804010,0x80000080000002,0x108040040101045,0x20c00004000102,0x400000100c0010,0x1300000040208,0x804000020010000,0x1008402002400080,0x201001000200040,0x4402000000806000,0x10402000000,0x1040008001200801,0x4080000000020400,0x10083080000002,0x8220140000040000,0x800084020100000,0x80010400010000,0x1200020108008060,0x180000000,0x400002400000018,0x4241000200,0x100800000000,0x10201008400483,0xc008000208201000,0x800420000100,0x2010002000410,0x28041000000,0x4010080000024,0x400480010010080,0x200040028000008,0x100810084020,0x20c0401000080000,0x1000240000220000,0x4000020800,0x410000000480000,0x8004008000804201,0x806020000104000,0x2080002000211000,0x1001008001000,0x20000010024000,0x480200002040000,0x48200044008000,0x100000000010080,0x80090400042,0x41040200800200,0x4000020100110,0x2000400082200010,0x1008200000000040,0x2004800002,0x2002010000080,];let p=(x%4095)as usize;(SQTABLE_MOD4095[p>>6]>>(p&63))&1==1}pub fn$issq_newton(x:$x)->bool{let sqrt_f=$sqrt_newton(x);sqrt_f*sqrt_f==x}pub fn$issq(x:$x)->bool{$issq_mod32(x)&&$issq_mod4095(x)&&$issq_newton(x)}pub fn$sqrt_exact(x:$x)->Option<$x>{if$issq_mod32(x)&&$issq_mod4095(x){let sqrt_f=$sqrt_newton(x);if sqrt_f*sqrt_f==x{return Some(sqrt_f);}}None}};}fn_isqrt_n!(sqrt_floor,isqrt_64_exact,issq_u64_newton,issq_u64_mod32,issq_u64_mod48,issq_u64_mod3960,issq_u64_mod4095,issq_u64,u64,32);fn_isqrt_n!(sqrt_floor,isqrt_32_exact,issq_u32_newton,issq_u32_mod32,issq_u32_mod48,issq_u32_mod3960,issq_u32_mod4095,issq_u32,u32,16);}
        pub mod jacobi {use crate::__cargo_equip::preludes::jacobi::*;use invariant::invariant;use primint::UPrimInt;pub fn jacobi_i64(ai:i64,n:u64)->i32{debug_assert_eq!(n&1,1);if ai<0{jacobi_inner(ai.wrapping_neg()as u64,n,if(n&3)==3{-1}else{1},)}else{jacobi_inner(ai as u64,n,1)}}pub fn jacobi_i32(ai:i32,n:u32)->i32{debug_assert_eq!(n&1,1);if ai<0{jacobi_inner(ai.wrapping_neg()as u32,n,if(n&3)==3{-1}else{1},)}else{jacobi_inner(ai as u32,n,1)}}pub fn jacobi<U:UPrimInt>(a:U,n:U)->i32{debug_assert_eq!(n.as_u32()%2,1);jacobi_inner(a,n,1)}fn jacobi_inner<U:UPrimInt>(mut a:U,mut n:U,mut j:i32)->i32{while!a.is_zero()&&n>U::from(255){let ba=a.trailing_zeros();if(ba&1)!=0&&((n+U::from(2))&U::from(5))==U::from(5){j=-j;}a>>=ba;if(a&n&U::from(3))==U::from(3){j=-j;}invariant!(!a.is_zero());let t=n%a;n=a;a=t;if a>(n>>1){a=n-a;if(n&U::from(3))==U::from(3){j=-j;}}}while!a.is_zero(){let ba=a.trailing_zeros();if(ba&1)!=0&&((n+U::from(2))&U::from(5))==U::from(5){j=-j;}a>>=ba;if a<n{if a>(n>>1){a=n-a;if(n&U::from(3))==U::from(3){j=-j;}let ba=a.trailing_zeros();if(ba&1)!=0&&((n+U::from(2))&U::from(5))==U::from(5){j=-j;}a>>=ba;}if(a&n&U::from(3))==U::from(3){j=-j;}let t=n-a;n=a;a=t;}else{a-=n;}}if n==U::from(1){j}else{0}}}
        pub mod modint32dynamic {use crate::__cargo_equip::preludes::modint32dynamic::*;pub enum ModIntDynType{Zero,Odd,P0998244353,P1000000007,Power2,Even,}pub struct ModIntDyn{ty:ModIntDynType,m:u32,tz:u32,mx:u32,mimx:u32,mym:u32,dim:u64,dimx:u64,ib:[u32;64],}impl ModIntDyn{pub fn new_modulus(m:u32)->Self{if m==0{return Self{m,ty:ModIntDynType::Zero,tz:32,mx:1,mimx:0,mym:!0u32,dim:1,dimx:0,ib:[1u32;64],};}let tz=m.trailing_zeros();let mx=m>>tz;let mimx={let mut t=mx.wrapping_mul(3)^2;let mut u=1u32.wrapping_sub(t.wrapping_mul(mx));t=t.wrapping_mul(u.wrapping_add(1));u=u.wrapping_mul(u);t=t.wrapping_mul(u.wrapping_add(1));u=u.wrapping_mul(u);t=t.wrapping_mul(u.wrapping_add(1));t};let mym=u32::from(tz!=0).wrapping_neg()>>((32-tz)&31);let dim=((!0u64)/u64::from(m)).wrapping_add(1);let dimx=((!0u64)/u64::from(mx)).wrapping_add(1);let mut ib=[0u32;64];let mut t=1;for e in ib.iter_mut(){*e=t;t=t/2+((t%2).wrapping_neg()&(mx/2+1));}Self{m,ty:{if m==998_244_353{ModIntDynType::P0998244353}else if m==1_000_000_007{ModIntDynType::P1000000007}else if tz==0{ModIntDynType::Odd}else if mx==1{ModIntDynType::Power2}else{ModIntDynType::Even}},tz,mx,mimx,mym,dim,dimx,ib,}}pub fn modulus(&self)->u32{self.m}#[inline]pub fn norm(&self,a:u32)->u32{match self.ty{ModIntDynType::Zero=>a,ModIntDynType::Power2=>a&self.mym,_=>{if a>=self.m{a%self.m}else{a}}}}#[inline]pub fn add(&self,a:u32,b:u32)->u32{debug_assert!(a<self.m);debug_assert!(b<self.m);let v=u64::from(a)+u64::from(b);match self.ty{ModIntDynType::Zero=>v as u32,_=>match v.overflowing_sub(u64::from(self.m)){(_,true)=>v as u32,(w,false)=>w as u32,},}}#[inline]pub fn sub(&self,a:u32,b:u32)->u32{debug_assert!(a<self.m);debug_assert!(b<self.m);let(v,f)=a.overflowing_sub(b);match self.ty{ModIntDynType::Zero=>v,_=>v.wrapping_add(u32::from(f).wrapping_neg()&self.m),}}#[inline]pub fn neg(&self,a:u32)->u32{debug_assert!(a<self.m);self.sub(0,a)}#[inline]pub fn mul(&self,a:u32,b:u32)->u32{debug_assert!(a<self.m);debug_assert!(b<self.m);let z=u64::from(a)*u64::from(b);match self.ty{ModIntDynType::Power2=>(z as u32)&self.mym,ModIntDynType::P0998244353=>{(z-(((u128::from(z)*0x89AE_4087_5DE0_CC3F)>>93)as u64)*998_244_353)as u32}ModIntDynType::P1000000007=>{(z-(((u128::from(z)*0x8970_5F31_12A2_8FE5)>>93)as u64)*1_000_000_007)as u32}ModIntDynType::Zero=>z as u32,ModIntDynType::Odd|ModIntDynType::Even=>{let x=((u128::from(z)*u128::from(self.dim))>>64)as u64;let(v,f)=z.overflowing_sub(x.wrapping_mul(u64::from(self.m)));(v as u32).wrapping_add(u32::from(f).wrapping_neg()&self.m)}}}#[inline]fn mulmx(&self,a:u32,b:u32)->u32{debug_assert!(a<self.mx);debug_assert!(b<self.mx);let z=u64::from(a)*u64::from(b);match self.ty{ModIntDynType::P0998244353=>{(z-(((u128::from(z)*0x89AE_4087_5DE0_CC3F)>>93)as u64)*998_244_353)as u32}ModIntDynType::P1000000007=>{(z-(((u128::from(z)*0x8970_5F31_12A2_8FE5)>>93)as u64)*1_000_000_007)as u32}ModIntDynType::Power2|ModIntDynType::Zero=>0,ModIntDynType::Odd|ModIntDynType::Even=>{let x=((u128::from(z)*u128::from(self.dimx))>>64)as u64;let(v,f)=z.overflowing_sub(x.wrapping_mul(u64::from(self.mx)));(v as u32).wrapping_add(u32::from(f).wrapping_neg()&self.mx)}}}#[inline]pub fn pow(&self,a:u32,mut b:u32)->u32{debug_assert!(a<self.m);if b==0{return(self.m>1)as u32;}let mut t=a;while b%2==0{t=self.mul(t,t);b/=2;}let mut r=t;b/=2;while b!=0{t=self.mul(t,t);if b%2!=0{r=self.mul(r,t);}b/=2;}r}#[inline]pub fn div(&self,a:u32,b:u32)->Option<u32>{debug_assert!(a<self.m);debug_assert!(b<self.m);self.inv(b).map(|ib|self.mul(a,ib))}#[inline]pub fn div2(&self,a:u32)->u32{debug_assert_eq!(self.m%2,1);if a%2==0{a/2}else{(a/2)+(self.m/2)+1}}#[inline]pub fn inv_plain(&self,n:u32)->Option<u32>{let m=self.m;let(mut a,mut b,mut x,mut y)=(1,0,n,m);if m==1{return Some(0);}loop{match x{0=>return None,1=>return Some(a),_=>{}}b+=a*(y/x);y%=x;match y{0=>return None,1=>return Some(m-b),_=>{}}a+=b*(x/y);x%=y;}}#[inline]fn inv_mx(&self,n:u32)->Option<u32>{debug_assert_ne!(self.mx%2,0);if self.mx%2==0{unsafe{core::hint::unreachable_unchecked()}}if self.mx==1{return Some(0);}let(mut a,mut b,mut x,mut y)=(1,0,n,self.mx);if x==0{return None;}let mut s=x.trailing_zeros();x>>=s;loop{if x==1{return Some(self.mulmx(a,self.ib[s as usize]));}if x==y{return None;}if x<=(y>>3){if x==0{unsafe{core::hint::unreachable_unchecked()}}b+=a*(y/x);y%=x;if y==0{return None;}let t=y.trailing_zeros();y>>=t;a<<=t;s+=t;}else{while x<y{b+=a;y-=x;let t=y.trailing_zeros();y>>=t;a<<=t;s+=t;}}if y==1{return Some(self.mulmx(self.mx-b,self.ib[s as usize]));}if(x>>3)>=y{if y==0{unsafe{core::hint::unreachable_unchecked()}}a+=b*(x/y);x%=y;if x==0{return None;}let t=x.trailing_zeros();x>>=t;b<<=t;s+=t;}else{while x>y{a+=b;x-=y;let t=x.trailing_zeros();x>>=t;b<<=t;s+=t;}}}}#[inline]fn inv_my(&self,n:u32)->Option<u32>{if self.mym==0{return Some(0);}if n%2==0{return None;}Some(match self.tz{21..=0xffff_ffff=>{let mut t=n.wrapping_mul(3)^2;let mut u=1u32.wrapping_sub(t.wrapping_mul(n));t=t.wrapping_mul(u.wrapping_add(1));u=u.wrapping_mul(u);t=t.wrapping_mul(u.wrapping_add(1));u=u.wrapping_mul(u);t=t.wrapping_mul(u.wrapping_add(1));t}11..=20=>{let mut t=n.wrapping_mul(3)^2;let mut u=1u32.wrapping_sub(t.wrapping_mul(n));t=t.wrapping_mul(u.wrapping_add(1));u=u.wrapping_mul(u);t=t.wrapping_mul(u.wrapping_add(1));t}6..=10=>{let t=n.wrapping_mul(3)^2;t.wrapping_mul(2u32.wrapping_sub(n.wrapping_mul(t)))}4..=5=>n.wrapping_mul(3)^2,0..=3=>n,}&self.mym,)}#[inline]pub fn inv(&self,n:u32)->Option<u32>{match self.ty{ModIntDynType::Power2=>self.inv_my(n),ModIntDynType::P0998244353|ModIntDynType::P1000000007|ModIntDynType::Odd=>{self.inv_mx(n)}ModIntDynType::Even=>{if let Some(y)=self.inv_my(n){if let Some(x)=self.inv_mx(n){let(t,f)=x.overflowing_sub(self.mx*(self.mimx.wrapping_mul(x.wrapping_sub(y))&self.mym),);return Some(t.wrapping_add(u32::from(f).wrapping_neg()&self.m));}}None}ModIntDynType::Zero=>{if n%2==0{return None;}let mut t=n.wrapping_mul(3)^2;let mut u=1u32.wrapping_sub(t.wrapping_mul(n));t=t.wrapping_mul(u.wrapping_add(1));u=u.wrapping_mul(u);t=t.wrapping_mul(u.wrapping_add(1));u=u.wrapping_mul(u);t=t.wrapping_mul(u.wrapping_add(1));Some(t)}}}}}
        pub mod montodd {use crate::__cargo_equip::preludes::montodd::*;use crate::__cargo_equip::crates::invariant::invariant;pub trait MontVal<T,BitCountType=u32>{fn n(&self)->T;fn ni(&self)->T;fn nh(&self)->T;fn r(&self)->T;fn rn(&self)->T;fn r2(&self)->T;fn d(&self)->T;fn k(&self)->BitCountType;}pub trait MontOps<T,BitCountType=u32>{fn add(&self,a:T,b:T)->T;fn sub(&self,a:T,b:T)->T;fn div2(&self,ar:T)->T;fn mrmul(&self,ar:T,br:T)->T;fn mr(&self,ar:T)->T;fn ar(&self,a:T)->T;fn pow(&self,ar:T,b:T)->T;}pub trait MontModN<T,BitCountType=u32>{fn modn(&self,x:T)->T;}pub trait MontNew<T,U=T,BitCountType=u32>{fn new(n:T)->Self;}pub struct Mont<T,BitCountType=u32>{n:T,ni:T,nh:T,r:T,rn:T,r2:T,d:T,k:BitCountType,}macro_rules!impl_mont_val_pr{($x:ty)=>{impl MontVal<$x>for Mont<$x>{fn n(&self)->$x{self.n}fn ni(&self)->$x{self.ni}fn nh(&self)->$x{self.nh}fn r(&self)->$x{self.r}fn rn(&self)->$x{self.rn}fn r2(&self)->$x{self.r2}fn d(&self)->$x{self.d}fn k(&self)->u32{self.k}}};}impl_mont_val_pr!(u64);impl_mont_val_pr!(u32);macro_rules!impl_mont_ops{($x:ty,$y:ty,$y2:ty,$w:literal)=>{impl MontOps<$y>for$x{fn add(&self,a:$y,b:$y)->$y{debug_assert!(a<self.n());debug_assert!(b<self.n());let(t,f)=a.overflowing_sub(self.n.wrapping_sub(b));t.wrapping_add((f as$y).wrapping_neg()&self.n())}fn sub(&self,a:$y,b:$y)->$y{debug_assert!(a<self.n());debug_assert!(b<self.n());let(t,f)=a.overflowing_sub(b);t.wrapping_add((f as$y).wrapping_neg()&self.n())}fn div2(&self,ar:$y)->$y{debug_assert!(ar<self.n());let t=ar>>1;t.wrapping_add((((ar&1)!=0)as$y).wrapping_neg()&self.nh())}fn mrmul(&self,ar:$y,br:$y)->$y{debug_assert!(ar<self.n());debug_assert!(br<self.n());let(n,ni)=(self.n(),self.ni());let t:$y2=(ar as$y2)*(br as$y2);let(t,f)=((t>>$w)as$y).overflowing_sub((((((t as$y).wrapping_mul(ni))as$y2)*(n as$y2))>>$w)as$y,);t.wrapping_add((f as$y).wrapping_neg()&n)}fn mr(&self,ar:$y)->$y{debug_assert!(ar<self.n());let(n,ni)=(self.n(),self.ni());let(t,f)=(((((ar.wrapping_mul(ni))as$y2)*(n as$y2))>>$w)as$y).overflowing_neg();t.wrapping_add((f as$y).wrapping_neg()&n)}fn ar(&self,a:$y)->$y{debug_assert!(a<self.n());self.mrmul(a,self.r2())}fn pow(&self,mut ar:$y,mut b:$y)->$y{debug_assert!(ar<self.n());if b==0{return self.r();}while b&1==0{ar=self.mrmul(ar,ar);b>>=1;}let mut t=ar;b>>=1;while b!=0{ar=self.mrmul(ar,ar);if(b&1)!=0{t=self.mrmul(t,ar);}b>>=1;}t}}};}impl_mont_ops!(Mont<u64>,u64,u128,64);impl_mont_ops!(Mont<u32>,u32,u64,32);macro_rules!impl_mont_modn{($x:ty)=>{impl MontModN<$x>for Mont<$x>{fn modn(&self,x:$x)->$x{if x<self.n(){x}else{x%self.n()}}}};}impl_mont_modn!(u64);impl_mont_modn!(u32);macro_rules!impl_mont_new{($x:ty,$x2:ty)=>{impl MontNew<$x>for Mont<$x>{fn new(n:$x)->Self{debug_assert!(n>1&&(n&1)==1);let ni={let bits=(!(0 as$x)).count_ones();let mut x=n.wrapping_mul(3)^2;let mut y=(1 as$x).wrapping_sub(n.wrapping_mul(x));let mut w=5;while w<bits{x=x.wrapping_mul(y.wrapping_add(1));y=y.wrapping_mul(y);w*=2;}x};debug_assert_eq!(n.wrapping_mul(ni),1);let nh=(n>>1)+1;invariant!(n!=0);let(r,r2)=((((1 as$x).wrapping_neg()%n).wrapping_add(1)),((((1 as$x2).wrapping_neg()%(n as$x2))as$x).wrapping_add(1)),);let rn=n-r;let mut d=n-1;let k=d.trailing_zeros();d>>=k;debug_assert_eq!(Self{n,ni,nh,r,rn,r2,d,k}.mr(r),1);debug_assert_eq!(Self{n,ni,nh,r,rn,r2,d,k}.mrmul(1,r2),r);Self{n,ni,nh,r,rn,r2,d,k,}}}};}impl_mont_new!(u64,u128);impl_mont_new!(u32,u64);}
        pub mod sqrt {use crate::__cargo_equip::preludes::sqrt::*;use invariant::invariant;use primint::UPrimInt;pub fn sqrt_floor<U:UPrimInt>(x:U)->U{if x<=U::one(){return x;}let k=(U::BITS>>1)-((x-U::one()).leading_zeros()>>1);let mut s=U::one()<<k;let mut t=(s+(x>>k))>>1;while t<s{s=t;invariant!(!s.is_zero());t=(s+x/s)>>1;}s}pub fn sqrt_ceil<U:UPrimInt>(x:U)->U{let s=sqrt_floor(x);if x>s*s{s+U::one()}else{s}}}
        pub mod input {use crate::__cargo_equip::preludes::input::*;pub use crate::__cargo_equip::macros::input::*;use crate::__cargo_equip::crates::invariant::invariant;use crate::__cargo_equip::crates::primint::{IPrimInt,UPrimInt};use std::convert::TryInto;#[macro_export]macro_rules!__cargo_equip_macro_def_input_input_inner{($source:expr)=>{};($source:expr,)=>{};($source:expr,mut$var:ident:$t:tt$($r:tt)*)=>{let mut$var=read_value!($source,$t);input_inner!{$source$($r)*}};($source:expr,$var:ident:$t:tt$($r:tt)*)=>{let$var=read_value!($source,$t);input_inner!{$source$($r)*}};}macro_rules!input_inner{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_input_input_inner!{$($tt)*})}#[macro_export]macro_rules!__cargo_equip_macro_def_input_read_value{($source:expr,($($t:tt),*))=>{($(read_value!($source,$t)),*)};($source:expr,[$t:tt;$len:expr])=>{(0..$len).map(|_|fread_value!($source,$t)).collect::<Vec<_>>()};($source:expr,u128)=>{$source.next_wordtoken().as_slice().parse_u128_raw()};($source:expr,usize)=>{$source.next_wordtoken().as_slice().parse_u64_raw()as usize};($source:expr,usize1)=>{$source.next_wordtoken().as_slice().parse_u64_raw()as usize-1};($source:expr,u64)=>{$source.next_wordtoken().as_slice().parse_u64_raw()};($source:expr,u64_1)=>{$source.next_wordtoken().as_slice().parse_u64_raw()-1};($source:expr,u32)=>{$source.next_wordtoken().as_slice().parse_u32_raw()};($source:expr,u32_1)=>{$source.next_wordtoken().as_slice().parse_u32_raw()-1};($source:expr,u16)=>{$source.next_wordtoken().as_slice().parse_u16_raw()};($source:expr,u16_1)=>{$source.next_wordtoken().as_slice().parse_u16_raw()-1};($source:expr,u8)=>{$source.next_wordtoken().as_slice().parse_u8_raw()};($source:expr,i128)=>{$source.next_wordtoken().as_slice().parse_i128_raw()};($source:expr,isize)=>{$source.next_wordtoken().as_slice().parse_i64_raw()as isize};($source:expr,i64)=>{$source.next_wordtoken().as_slice().parse_i64_raw()};($source:expr,i32)=>{$source.next_wordtoken().as_slice().parse_i32_raw()};($source:expr,i16)=>{$source.next_wordtoken().as_slice().parse_i16_raw()};($source:expr,i8)=>{$source.next_wordtoken().as_slice().parse_i8_raw()};($source:expr,byte)=>{$source.get_ascii_byte()};($source:expr,Bytes)=>{{$source.next_wordtoken().as_vec()}};($source:expr,BytesToken)=>{{$source.next_wordtoken()}};($source:expr,String)=>{unsafe{$source.next_wordtoken().as_string_unchecked()}};($source:expr,LineBytes)=>{{$source.next_linetoken().as_vec()}};($source:expr,LineBytesToken)=>{{$source.next_linetoken()}};($source:expr,LineString)=>{unsafe{$source.next_linetoken().as_string_unchecked()}};($source:expr,$t:ty)=>{{unsafe{String::from_utf8_unchecked($source.next_wordtoken().as_slice())}.parse::<$t>().expect("Parse error")}};}macro_rules!read_value{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_input_read_value!{$($tt)*})}unsafe fn ptr_offset_u8(dist:*const u8,origin:*const u8)->usize{dist as usize-origin as usize}#[derive(Clone,Debug)]pub enum Token<'a>{Slice(&'a[u8]),Bytes(Vec<u8>),}impl Token<'_>{pub fn as_slice(&self)->&[u8]{match self{Self::Slice(s)=>s,Self::Bytes(v)=>v.as_slice(),}}pub fn as_vec(self)->Vec<u8>{match self{Self::Slice(s)=>s.to_vec(),Self::Bytes(v)=>v,}}pub fn as_string(self)->Result<String,std::string::FromUtf8Error>{String::from_utf8(self.as_vec())}pub unsafe fn as_string_unchecked(self)->String{String::from_utf8_unchecked(self.as_vec())}}pub trait NextToken{fn next_wordtoken(&mut self)->Token;fn next_linetoken(&mut self)->Token;}pub struct BytesIter<'a>(pub&'a[u8]);impl NextToken for BytesIter<'_>{fn next_wordtoken(&mut self)->Token{while let[first,remain@..]=self.0{if*first<0x21{self.0=remain;}else{break;}}let mut split2=self.0.splitn(2,|&c|c<0x21);let cur=split2.next().unwrap_or(b"");self.0=split2.next().unwrap_or(b"");Token::Slice(cur)}fn next_linetoken(&mut self)->Token{while let[first,remain@..]=self.0{if*first<0x21{self.0=remain;}else{break;}}let mut split2=self.0.splitn(2,|&c|c==b'\n');let mut cur:&[u8]=split2.next().unwrap_or(b"");while let[remain@..,last]=cur{if*last<0x21{cur=remain;}else{break;}}self.0=split2.next().unwrap_or(b"");Token::Slice(cur)}}pub struct ProconIBufIter<R:std::io::BufRead>{inner:R,raw:*const u8,ptr:*const u8,end:*const u8,len:usize,balign:*const u8,wmask:Vec<u64>,}impl<R:std::io::BufRead>ProconIBufIter<R>{pub fn new(inner:R)->Self{const EMPTY_U8_SLICE:&'static[u8]=b"";Self{inner,raw:EMPTY_U8_SLICE.as_ptr(),ptr:EMPTY_U8_SLICE.as_ptr(),end:EMPTY_U8_SLICE.as_ptr(),len:0,balign:EMPTY_U8_SLICE.as_ptr(),wmask:vec![0u64;200],}}}impl<R:std::io::BufRead>ProconIBufIter<R>{pub fn buf_empty(&self)->bool{self.ptr==self.end}#[allow(clippy::missing_safety_doc)]#[cold]unsafe fn inner_read(&mut self)->bool{invariant!(self.ptr==self.end);self.inner.consume(ptr_offset_u8(self.ptr,self.raw));if let Ok(s)=self.inner.fill_buf(){self.raw=s.as_ptr();self.ptr=s.as_ptr();self.end=s.as_ptr().add(s.len());self.len=s.len();self.balign=(self.raw as usize&!0x3f)as*const u8;let alignlen=(((self.end as usize)+0x3f)&(!0x3f))-self.balign as usize;let wmasklen=(alignlen+63)/64;#[cfg(target_arch="x86_64")]{#[target_feature(enable="avx2")]unsafe fn genmask_avx2(asl:&[u8],bsl:&mut[u64]){use std::arch::x86_64::*;let diff=_mm256_set1_epi8(-0x21);for(a,b)in asl.chunks_exact(64).zip(bsl.iter_mut()){let s0=_mm256_load_si256(std::mem::transmute(a.as_ptr().add(0)));let s1=_mm256_load_si256(std::mem::transmute(a.as_ptr().add(32)));let a0=_mm256_add_epi8(s0,diff);let a1=_mm256_add_epi8(s1,diff);let m0=_mm256_movemask_epi8(_mm256_andnot_si256(s0,a0))as u32;let m1=_mm256_movemask_epi8(_mm256_andnot_si256(s1,a1))as u32;*b=((m1 as u64)<<32)|(m0 as u64);}}unsafe fn genmask_sse2(asl:&[u8],bsl:&mut[u64]){use std::arch::x86_64::*;let diff=_mm_set1_epi8(-0x21);for(a,b)in asl.chunks_exact(64).zip(bsl.iter_mut()){let s0=_mm_load_si128(std::mem::transmute(a.as_ptr().add(0)));let s1=_mm_load_si128(std::mem::transmute(a.as_ptr().add(16)));let s2=_mm_load_si128(std::mem::transmute(a.as_ptr().add(32)));let s3=_mm_load_si128(std::mem::transmute(a.as_ptr().add(48)));let a0=_mm_add_epi8(s0,diff);let a1=_mm_add_epi8(s1,diff);let a2=_mm_add_epi8(s2,diff);let a3=_mm_add_epi8(s3,diff);let m0=_mm_movemask_epi8(_mm_andnot_si128(s0,a0))as u16;let m1=_mm_movemask_epi8(_mm_andnot_si128(s1,a1))as u16;let m2=_mm_movemask_epi8(_mm_andnot_si128(s2,a2))as u16;let m3=_mm_movemask_epi8(_mm_andnot_si128(s3,a3))as u16;*b=((m3 as u64)<<48)|((m2 as u64)<<32)|((m1 as u64)<<16)|(m0 as u64);}}if self.wmask.len()<=wmasklen{self.wmask.extend(std::iter::repeat(0).take(wmasklen+1-self.wmask.len()));}let asl=std::slice::from_raw_parts(self.balign,wmasklen*64);if is_x86_feature_detected!("avx2"){genmask_avx2(asl,&mut self.wmask);}else{genmask_sse2(asl,&mut self.wmask);}};self.len!=0}else{self.raw=self.ptr;self.len=self.end as usize-self.ptr as usize;false}}#[allow(clippy::missing_safety_doc)]unsafe fn next_unchecked(&mut self)->u8{let p=self.ptr;self.ptr=p.add(1);*p}pub fn skipuntil_bytes_fn<F:FnMut(u8)->bool>(&mut self,f:&mut F)->bool{loop{let mut ptr=self.ptr;while ptr!=self.end{if f(unsafe{*ptr}){self.ptr=ptr;return true;}unsafe{ptr=ptr.add(1);}}self.ptr=ptr;if unsafe{!self.inner_read()}{return false;}}}pub fn get_ascii_bytes(&mut self,vec:&mut Vec<u8>){if!self.skipuntil_bytes_fn(&mut|c:u8|c>b' '){return;}#[cfg(target_arch="x86_64")]unsafe{let ptr=self.ptr;let pdiff=(self.ptr as usize)-(self.balign as usize)+1;let(p64q,p64r)=(pdiff/64,pdiff%64);let mut w=self.wmask.as_ptr().add(p64q);let wmask=(*w)&((!0u64)<<p64r);let mut p=self.balign.add(p64q*64);if wmask!=0{p=p.add(wmask.trailing_zeros()as usize);if p<self.end{self.ptr=p.add(1);vec.extend_from_slice(std::slice::from_raw_parts(ptr,p as usize-ptr as usize,));return;}}p=p.add(64);w=w.add(1);let end64=self.end.sub(64);while p<end64{let wmask=*w;if wmask!=0{let tlz=wmask.trailing_zeros();let pp=p.add(tlz as usize);self.ptr=pp.add(1);vec.extend_from_slice(std::slice::from_raw_parts(ptr,pp as usize-ptr as usize,));return;}p=p.add(64);w=w.add(1);}if p<self.end{let wmask=*w;if wmask!=0{let tlz=wmask.trailing_zeros();let pp=p.add(tlz as usize);if pp<self.end{self.ptr=pp.add(1);vec.extend_from_slice(std::slice::from_raw_parts(ptr,pp as usize-ptr as usize,));return;}}}vec.extend_from_slice(std::slice::from_raw_parts(ptr,self.end as usize-ptr as usize,));loop{self.ptr=self.end;if!self.inner_read(){return;}let ptr=self.ptr;let pdiff=(ptr as usize)-(self.balign as usize);let(p64q,p64r)=(pdiff/64,pdiff%64);let mut w=self.wmask.as_ptr().add(p64q);let mut wmask=(*w)&((!0u64)<<p64r);let mut p=self.balign.add(p64q*64);while p<self.end{if wmask!=0{p=p.add(wmask.trailing_zeros()as usize);if p<self.end{self.ptr=p.add(1);vec.extend_from_slice(std::slice::from_raw_parts(ptr,p as usize-ptr as usize,));return;}break;}p=p.add(64);w=w.add(1);wmask=*w;}vec.extend_from_slice(std::slice::from_raw_parts(ptr,self.end as usize-ptr as usize,));}}#[cfg(not(target_arch="x86_64"))]unsafe{let ptr=self.ptr;let mut p=ptr.add(1);while p<self.end{if*p<=b' '{self.ptr=p.add(1);vec.extend_from_slice(std::slice::from_raw_parts(ptr,p as usize-ptr as usize,));return;}p=p.add(1);}vec.extend_from_slice(std::slice::from_raw_parts(ptr,self.end as usize-ptr as usize,));loop{self.ptr=self.end;if!self.inner_read(){break;}let ptr=self.ptr;let mut p=ptr;while p<self.end{if*p<=b' '{self.ptr=p.add(1);vec.extend_from_slice(std::slice::from_raw_parts(ptr,p as usize-ptr as usize,));return;}p=p.add(1);}vec.extend_from_slice(std::slice::from_raw_parts(ptr,self.end as usize-ptr as usize,));}return;}}}impl<R:std::io::BufRead>NextToken for ProconIBufIter<R>{#[inline]fn next_wordtoken(&mut self)->Token{if!self.skipuntil_bytes_fn(&mut|c:u8|c>b' '){return Token::Slice(b"");}#[cfg(target_arch="x86_64")]unsafe{let ptr=self.ptr;let pdiff=(self.ptr as usize)-(self.balign as usize)+1;let(p64q,p64r)=(pdiff/64,pdiff%64);let mut w=self.wmask.as_ptr().add(p64q);let wmask=(*w)&((!0u64)<<p64r);let mut p=self.balign.add(p64q*64);if wmask!=0{p=p.add(wmask.trailing_zeros()as usize);if p<self.end{self.ptr=p.add(1);return Token::Slice(std::slice::from_raw_parts(ptr,p as usize-ptr as usize,));}}p=p.add(64);w=w.add(1);let end64=self.end.sub(64);while p<end64{let wmask=*w;if wmask!=0{let tlz=wmask.trailing_zeros();let pp=p.add(tlz as usize);self.ptr=pp.add(1);return Token::Slice(std::slice::from_raw_parts(ptr,pp as usize-ptr as usize,));}p=p.add(64);w=w.add(1);}if p<self.end{let wmask=*w;if wmask!=0{let tlz=wmask.trailing_zeros();let pp=p.add(tlz as usize);if pp<self.end{self.ptr=pp.add(1);return Token::Slice(std::slice::from_raw_parts(ptr,pp as usize-ptr as usize,));}}}let mut v=std::slice::from_raw_parts(ptr,self.end as usize-ptr as usize).to_vec();loop{self.ptr=self.end;if!self.inner_read(){return Token::Bytes(v);}let ptr=self.ptr;let pdiff=(ptr as usize)-(self.balign as usize);let(p64q,p64r)=(pdiff/64,pdiff%64);let mut w=self.wmask.as_ptr().add(p64q);let mut wmask=(*w)&((!0u64)<<p64r);let mut p=self.balign.add(p64q*64);while p<self.end{if wmask!=0{p=p.add(wmask.trailing_zeros()as usize);if p<self.end{self.ptr=p.add(1);v.extend_from_slice(std::slice::from_raw_parts(ptr,p as usize-ptr as usize,));return Token::Bytes(v);}break;}p=p.add(64);w=w.add(1);wmask=*w;}v.extend_from_slice(std::slice::from_raw_parts(ptr,self.end as usize-ptr as usize,));}}#[cfg(not(target_arch="x86_64"))]unsafe{let ptr=self.ptr;let mut p=ptr.add(1);while p<self.end{if*p<=b' '{self.ptr=p.add(1);return Token::Slice(std::slice::from_raw_parts(ptr,p as usize-ptr as usize,));}p=p.add(1);}let mut v=std::slice::from_raw_parts(ptr,self.end as usize-ptr as usize).to_vec();loop{self.ptr=self.end;if!self.inner_read(){break;}let ptr=self.ptr;let mut p=ptr;while p<self.end{if*p<=b' '{self.ptr=p.add(1);v.extend_from_slice(std::slice::from_raw_parts(ptr,p as usize-ptr as usize,));return Token::Bytes(v);}p=p.add(1);}v.extend_from_slice(std::slice::from_raw_parts(ptr,self.end as usize-ptr as usize,));}return Token::Bytes(v);}}#[inline]fn next_linetoken(&mut self)->Token{if!self.skipuntil_bytes_fn(&mut|c:u8|c>=b' '){return Token::Slice(b"");}#[cfg(target_arch="x86_64")]unsafe{let ptr=self.ptr;let pdiff=(self.ptr as usize)-(self.balign as usize)+1;let(p64q,p64r)=(pdiff/64,pdiff%64);let mut w=self.wmask.as_ptr().add(p64q);let mut wmask=(*w)&((!0u64)<<p64r);let mut p=self.balign.add(p64q*64);'s:while p<self.end{while wmask!=0{let tlz=wmask.trailing_zeros();let pp=p.add(tlz as usize);if pp>=self.end{break 's;}if*pp<b' '{self.ptr=pp.add(1);return Token::Slice(std::slice::from_raw_parts(ptr,pp as usize-ptr as usize,));}wmask&=wmask.wrapping_sub(1);}p=p.add(64);w=w.add(1);wmask=*w;}let mut v=std::slice::from_raw_parts(ptr,self.end as usize-ptr as usize).to_vec();loop{self.ptr=self.end;if!self.inner_read(){break;}let ptr=self.ptr;let pdiff=(ptr as usize)-(self.balign as usize);let(p64q,p64r)=(pdiff/64,pdiff%64);let mut w=self.wmask.as_ptr().add(p64q);let mut wmask=(*self.wmask.get_unchecked(p64q))&((!0u64)<<p64r);let mut p=self.balign.add(p64q*64);'v:while p<self.end{while wmask!=0{let tlz=wmask.trailing_zeros();let pp=p.add(tlz as usize);if pp>=self.end{break 'v;}assert!(*pp<b' ');if(*pp)<b' '{self.ptr=pp.add(1);v.extend_from_slice(std::slice::from_raw_parts(ptr,pp as usize-ptr as usize,));return Token::Bytes(v);}wmask&=wmask.wrapping_sub(1);}p=p.add(64);w=w.add(1);wmask=*w;}v.extend_from_slice(std::slice::from_raw_parts(ptr,self.end as usize-ptr as usize,));}return Token::Bytes(v);}#[cfg(not(target_arch="x86_64"))]unsafe{let ptr=self.ptr;let mut p=ptr.add(1);while p<self.end{if*p<b' '{self.ptr=p.add(1);return Token::Slice(std::slice::from_raw_parts(ptr,p as usize-ptr as usize,));}p=p.add(1);}let mut v=std::slice::from_raw_parts(ptr,self.end as usize-ptr as usize).to_vec();loop{self.ptr=self.end;if!self.inner_read(){break;}let ptr=self.ptr;let mut p=ptr;while p<self.end{if*p<b' '{self.ptr=p.add(1);v.extend_from_slice(std::slice::from_raw_parts(ptr,p as usize-ptr as usize,));return Token::Bytes(v);}p=p.add(1);}v.extend_from_slice(std::slice::from_raw_parts(ptr,self.end as usize-ptr as usize,));}return Token::Bytes(v);}}}impl<R:std::io::BufRead>Iterator for ProconIBufIter<R>{type Item=u8;fn next(&mut self)->Option<Self::Item>{if!self.buf_empty()||unsafe{self.inner_read()}{Some(unsafe{self.next_unchecked()})}else{None}}fn size_hint(&self)->(usize,Option<usize>){(usize::max_value(),None)}}#[inline]fn parseuint_arith8le(mut a:u64)->u64{a=(a&0x0f0f0f0f0f0f0f0f).wrapping_mul((10<<8)+1)>>8;a=(a&0x00ff00ff00ff00ff).wrapping_mul((100<<16)+1)>>16;(a&0x0000ffff0000ffff).wrapping_mul((1_0000<<32)+1)>>32}#[inline]#[allow(unused)]fn parseuint_arith8be(mut a:u64)->u64{a=(a&0x0f0f0f0f0f0f0f0f).wrapping_mul((1<<8)+10)>>8;a=(a&0x00ff00ff00ff00ff).wrapping_mul((1<<16)+100)>>16;(a&0x0000ffff0000ffff).wrapping_mul((1<<32)+1_0000)>>32}#[inline]fn parseuint_arith4le(mut a:u32)->u32{a=(a&0x0f0f0f0f).wrapping_mul((10<<8)+1)>>8;(a&0x00ff00ff).wrapping_mul((100<<16)+1)>>16}#[inline]#[allow(unused)]fn parseuint_arith4be(mut a:u32)->u32{a=(a&0x0f0f0f0f).wrapping_mul((1<<8)+10)>>8;(a&0x00ff00ff).wrapping_mul((1<<16)+100)>>16}#[inline]fn parseuint_arith2le(a:u16)->u16{(a&0x0f0f).wrapping_mul((10<<8)+1)>>8}#[inline]#[allow(unused)]fn parseuint_arith2be(a:u16)->u16{(a&0x0f0f).wrapping_mul((1<<8)+10)>>8}#[inline(always)]#[allow(unused)]fn parseuint_arith1(a:u8)->u8{a&0x0f}#[inline(always)]fn parseuint_raw32b(s:[u8;32])->u128{let a=parseuint_arith8le(u64::from_le_bytes(s[0..8].try_into().unwrap()));let b=parseuint_arith8le(u64::from_le_bytes(s[8..16].try_into().unwrap()));let c=parseuint_arith8le(u64::from_le_bytes(s[16..24].try_into().unwrap()));let d=parseuint_arith8le(u64::from_le_bytes(s[24..32].try_into().unwrap()));((a*1_0000_0000+b)as u128)*1_0000_0000_0000_0000+((c*1_0000_0000+d)as u128)}#[inline(always)]fn parseuint_raw16b(s:[u8;16])->u64{let a=parseuint_arith8le(u64::from_le_bytes(s[0..8].try_into().unwrap()));let b=parseuint_arith8le(u64::from_le_bytes(s[8..16].try_into().unwrap()));a*1_0000_0000+b}#[inline(always)]fn parseuint_raw8b(s:[u8;8])->u64{parseuint_arith8le(u64::from_le_bytes(s))}#[rustfmt::skip]#[inline(always)]fn parseuint_raw7b(s:&[u8])->u64{invariant!(s.len()<=8);match s.len(){0=>0,1=>parseuint_arith1(s[0])as u64,2=>parseuint_arith2le(u16::from_le_bytes(s[0..2].try_into().unwrap()))as u64,3=>parseuint_arith4le(((s[0]as u32)<<8)|((u16::from_le_bytes(s[1..3].try_into().unwrap())as u32)<<16))as u64,4=>parseuint_arith4le(u32::from_le_bytes(s[0..4].try_into().unwrap()))as u64,5=>parseuint_arith8le(((s[0]as u64)<<24)|((u32::from_le_bytes(s[1..5].try_into().unwrap())as u64)<<32)),6=>parseuint_arith8le(((u16::from_le_bytes(s[0..2].try_into().unwrap())as u64)<<16)|((u32::from_le_bytes(s[2..6].try_into().unwrap())as u64)<<32)),7=>parseuint_arith8le(((u32::from_le_bytes(s[0..4].try_into().unwrap())as u64)<<8)|((u32::from_le_bytes(s[3..7].try_into().unwrap())as u64)<<32)),_=>parseuint_arith8le(u64::from_le_bytes(s[0..8].try_into().unwrap())),}}#[inline(always)]fn parseuint_raw4b(s:[u8;4])->u32{parseuint_arith4le(u32::from_le_bytes(s))}#[rustfmt::skip]#[inline(always)]fn parseuint_raw3b(s:&[u8])->u32{invariant!(s.len()<=4);match s.len(){0=>0,1=>parseuint_arith1(s[0])as u32,2=>parseuint_arith2le(u16::from_le_bytes(s[0..2].try_into().unwrap()))as u32,3=>parseuint_arith4le(((s[0]as u32)<<8)|((u16::from_le_bytes(s[1..3].try_into().unwrap())as u32)<<16)),_=>parseuint_arith4le(u32::from_le_bytes(s[0..4].try_into().unwrap())),}}#[inline(always)]fn parseuint_raw2b(s:[u8;2])->u16{parseuint_arith2le(u16::from_le_bytes(s))}#[inline(always)]fn parseuint_raw1b(s:u8)->u8{parseuint_arith1(s)}pub trait ByteParseIntRaw{fn parse_u128_raw(&self)->u128;fn parse_u64_raw(&self)->u64;fn parse_u32_raw(&self)->u32;fn parse_u16_raw(&self)->u16;fn parse_u8_raw(&self)->u8;fn parse_i128_raw(&self)->i128;fn parse_i64_raw(&self)->i64;fn parse_i32_raw(&self)->i32;fn parse_i16_raw(&self)->i16;fn parse_i8_raw(&self)->i8;}impl ByteParseIntRaw for&[u8]{#[rustfmt::skip]#[inline(always)]fn parse_u128_raw(&self)->u128{invariant!(self.len()<=39);invariant!(self.iter().all(u8::is_ascii_digit));match self.len(){0=>0,1=>parseuint_raw1b(self[0])as u128,2=>parseuint_raw2b(self[0..2].try_into().unwrap())as u128,3=>parseuint_arith4le(((self[0]as u32)<<8)|((u16::from_le_bytes(self[1..3].try_into().unwrap())as u32)<<16))as u128,4=>parseuint_raw4b(self[0..4].try_into().unwrap())as u128,5=>parseuint_arith8le(((self[0]as u64)<<24)|((u32::from_le_bytes(self[1..5].try_into().unwrap())as u64)<<32))as u128,6=>parseuint_arith8le(((u16::from_le_bytes(self[0..2].try_into().unwrap())as u64)<<16)|((u32::from_le_bytes(self[2..6].try_into().unwrap())as u64)<<32))as u128,7=>parseuint_arith8le(((u32::from_le_bytes(self[0..4].try_into().unwrap())as u64)<<8)|((u32::from_le_bytes(self[3..7].try_into().unwrap())as u64)<<32))as u128,8=>parseuint_raw8b(self[0..8].try_into().unwrap())as u128,9=>((parseuint_raw1b(self[0])as u64)*1_0000_0000+parseuint_raw8b(self[1..9].try_into().unwrap()))as u128,10=>((parseuint_raw2b(self[0..2].try_into().unwrap())as u64)*1_0000_0000+parseuint_raw8b(self[2..10].try_into().unwrap()))as u128,11=>((parseuint_arith4le(u32::from_le_bytes(self[0..4].try_into().unwrap())<<8)as u64)*1_0000_0000+parseuint_raw8b(self[3..11].try_into().unwrap()))as u128,12=>((parseuint_raw4b(self[0..4].try_into().unwrap())as u64)*1_0000_0000+parseuint_raw8b(self[4..12].try_into().unwrap()))as u128,13=>(parseuint_arith8le(u64::from_le_bytes(self[0..8].try_into().unwrap())<<24)*1_0000_0000+parseuint_raw8b(self[5..13].try_into().unwrap()))as u128,14=>(parseuint_arith8le(u64::from_le_bytes(self[0..8].try_into().unwrap())<<16)*1_0000_0000+parseuint_raw8b(self[6..14].try_into().unwrap()))as u128,15=>(parseuint_arith8le(u64::from_le_bytes(self[0..8].try_into().unwrap())<<8)*1_0000_0000+parseuint_raw8b(self[7..15].try_into().unwrap()))as u128,16=>parseuint_raw16b(self[0..16].try_into().unwrap())as u128,17=>((parseuint_raw1b(self[0])as u64)*1_0000_0000_0000_0000+parseuint_raw16b(self[1..17].try_into().unwrap()))as u128,18=>((parseuint_raw2b(self[0..2].try_into().unwrap())as u64)*1_0000_0000_0000_0000+(parseuint_raw16b(self[2..18].try_into().unwrap())))as u128,19=>((parseuint_arith4le(u32::from_le_bytes(self[0..4].try_into().unwrap())<<8)as u64)*1_0000_0000_0000_0000+(parseuint_raw16b(self[3..19].try_into().unwrap())))as u128,20=>(parseuint_raw4b(self[0..4].try_into().unwrap())as u128)*1_0000_0000_0000_0000+(parseuint_raw16b(self[4..20].try_into().unwrap())as u128),21=>(parseuint_arith8le(u64::from_le_bytes(self[0..8].try_into().unwrap())<<24)as u128)*1_0000_0000_0000_0000+(parseuint_raw16b(self[5..21].try_into().unwrap())as u128),22=>(parseuint_arith8le(u64::from_le_bytes(self[0..8].try_into().unwrap())<<16)as u128)*1_0000_0000_0000_0000+(parseuint_raw16b(self[6..22].try_into().unwrap())as u128),23=>(parseuint_arith8le(u64::from_le_bytes(self[0..8].try_into().unwrap())<<8)as u128)*1_0000_0000_0000_0000+(parseuint_raw16b(self[7..23].try_into().unwrap())as u128),24=>(parseuint_raw8b(self[0..8].try_into().unwrap())as u128)*1_0000_0000_0000_0000+(parseuint_raw16b(self[8..24].try_into().unwrap())as u128),25=>(((parseuint_raw1b(self[0])as u64)*1_0000_0000+parseuint_raw8b(self[1..9].try_into().unwrap()))as u128)*1_0000_0000_0000_0000+(parseuint_raw16b(self[9..25].try_into().unwrap())as u128),26=>(((parseuint_raw2b(self[0..2].try_into().unwrap())as u64)*1_0000_0000+parseuint_raw8b(self[2..10].try_into().unwrap()))as u128)*1_0000_0000_0000_0000+(parseuint_raw16b(self[10..26].try_into().unwrap())as u128),27=>(((parseuint_arith4le(u32::from_le_bytes(self[0..4].try_into().unwrap())<<8)as u64)*1_0000_0000+parseuint_raw8b(self[3..11].try_into().unwrap()))as u128)*1_0000_0000_0000_0000+(parseuint_raw16b(self[11..27].try_into().unwrap())as u128),28=>(((parseuint_raw4b(self[0..4].try_into().unwrap())as u64)*1_0000_0000+parseuint_raw8b(self[4..12].try_into().unwrap()))as u128)*1_0000_0000_0000_0000+(parseuint_raw16b(self[12..28].try_into().unwrap())as u128),29=>(((parseuint_arith8le(u64::from_le_bytes(self[0..8].try_into().unwrap())<<24)as u64)*1_0000_0000+parseuint_raw8b(self[5..13].try_into().unwrap()))as u128)*1_0000_0000_0000_0000+(parseuint_raw16b(self[13..29].try_into().unwrap())as u128),30=>(((parseuint_arith8le(u64::from_le_bytes(self[0..8].try_into().unwrap())<<16)as u64)*1_0000_0000+parseuint_raw8b(self[6..14].try_into().unwrap()))as u128)*1_0000_0000_0000_0000+(parseuint_raw16b(self[14..30].try_into().unwrap())as u128),31=>(((parseuint_arith8le(u64::from_le_bytes(self[0..8].try_into().unwrap())<<8)as u64)*1_0000_0000+parseuint_raw8b(self[7..15].try_into().unwrap()))as u128)*1_0000_0000_0000_0000+(parseuint_raw16b(self[15..31].try_into().unwrap())as u128),32=>parseuint_raw32b(self[0..32].try_into().unwrap()),33=>parseuint_raw32b(self[0..32].try_into().unwrap())*10+(parseuint_raw1b(self[32])as u128),34=>parseuint_raw32b(self[0..32].try_into().unwrap())*100+(parseuint_raw2b(self[32..34].try_into().unwrap())as u128),35=>parseuint_raw32b(self[0..32].try_into().unwrap())*1000+(parseuint_arith4le(u32::from_le_bytes(self[31..35].try_into().unwrap())&0x0f0f0f00)as u128),36=>parseuint_raw32b(self[0..32].try_into().unwrap())*1_0000+(parseuint_raw4b(self[32..36].try_into().unwrap())as u128),37=>parseuint_raw32b(self[0..32].try_into().unwrap())*10_0000+(parseuint_arith8le(u64::from_le_bytes(self[29..37].try_into().unwrap())&0x0f0f0f0f_0f000000)as u128),38=>parseuint_raw32b(self[0..32].try_into().unwrap())*100_0000+(parseuint_arith8le(u64::from_le_bytes(self[30..38].try_into().unwrap())&0x0f0f0f0f_0f0f0000)as u128),_=>parseuint_raw32b(self[0..32].try_into().unwrap())*1000_0000+(parseuint_arith8le(u64::from_le_bytes(self[31..39].try_into().unwrap())&0x0f0f0f0f_0f0f0f00)as u128),}}#[rustfmt::skip]#[inline(always)]fn parse_u64_raw(&self)->u64{invariant!(self.len()<=20);invariant!(self.iter().all(u8::is_ascii_digit));match self.len(){0=>0,1=>parseuint_raw1b(self[0])as u64,2=>parseuint_raw2b(self[0..2].try_into().unwrap())as u64,3=>parseuint_arith4le(((self[0]as u32)<<8)|((u16::from_le_bytes(self[1..3].try_into().unwrap())as u32)<<16))as u64,4=>parseuint_raw4b(self[0..4].try_into().unwrap())as u64,5=>parseuint_arith8le(((self[0]as u64)<<24)|((u32::from_le_bytes(self[1..5].try_into().unwrap())as u64)<<32)),6=>parseuint_arith8le(((u16::from_le_bytes(self[0..2].try_into().unwrap())as u64)<<16)|((u32::from_le_bytes(self[2..6].try_into().unwrap())as u64)<<32)),7=>parseuint_arith8le(((u32::from_le_bytes(self[0..4].try_into().unwrap())as u64)<<8)|((u32::from_le_bytes(self[3..7].try_into().unwrap())as u64)<<32)),8=>parseuint_raw8b(self[0..8].try_into().unwrap()),9=>(parseuint_arith1(self[0])as u64)*1_0000_0000+parseuint_raw8b(self[1..9].try_into().unwrap()),10=>(parseuint_arith2le(u16::from_le_bytes(self[0..2].try_into().unwrap()))as u64)*1_0000_0000+parseuint_raw8b(self[2..10].try_into().unwrap()),11=>(parseuint_arith4le(u32::from_le_bytes(self[0..4].try_into().unwrap())<<8)as u64)*1_0000_0000+parseuint_raw8b(self[3..11].try_into().unwrap()),12=>(parseuint_arith4le(u32::from_le_bytes(self[0..4].try_into().unwrap()))as u64)*1_0000_0000+parseuint_raw8b(self[4..12].try_into().unwrap()),13=>parseuint_arith8le(u64::from_le_bytes(self[0..8].try_into().unwrap())<<24)*1_0000_0000+parseuint_raw8b(self[5..13].try_into().unwrap()),14=>parseuint_arith8le(u64::from_le_bytes(self[0..8].try_into().unwrap())<<16)*1_0000_0000+parseuint_raw8b(self[6..14].try_into().unwrap()),15=>parseuint_arith8le(u64::from_le_bytes(self[0..8].try_into().unwrap())<<8)*1_0000_0000+parseuint_raw8b(self[7..15].try_into().unwrap()),16=>parseuint_raw16b(self[0..16].try_into().unwrap()),17=>(parseuint_arith1(self[0])as u64)*1_0000_0000_0000_0000+parseuint_raw16b(self[1..17].try_into().unwrap()),18=>(parseuint_arith2le(u16::from_le_bytes(self[0..2].try_into().unwrap()))as u64)*1_0000_0000_0000_0000+parseuint_raw16b(self[2..18].try_into().unwrap()),19=>(parseuint_arith4le(u32::from_le_bytes(self[0..4].try_into().unwrap())<<8)as u64)*1_0000_0000_0000_0000+parseuint_raw16b(self[3..19].try_into().unwrap()),_=>(parseuint_arith4le(u32::from_le_bytes(self[0..4].try_into().unwrap()))as u64)*1_0000_0000_0000_0000+(parseuint_raw16b(self[4..20].try_into().unwrap())),}}#[rustfmt::skip]#[inline(always)]fn parse_u32_raw(&self)->u32{invariant!(self.len()<=10);invariant!(self.iter().all(u8::is_ascii_digit));match self.len(){0=>0,1=>parseuint_raw1b(self[0])as u32,2=>parseuint_raw2b(self[0..2].try_into().unwrap())as u32,3=>parseuint_arith4le(((self[0]as u32)<<8)|((u16::from_le_bytes(self[1..3].try_into().unwrap())as u32)<<16)),4=>parseuint_raw4b(self[0..4].try_into().unwrap()),5=>parseuint_arith8le(((self[0]as u64)<<24)|((u32::from_le_bytes(self[1..5].try_into().unwrap())as u64)<<32))as u32,6=>parseuint_arith8le(((u16::from_le_bytes(self[0..2].try_into().unwrap())as u64)<<16)|((u32::from_le_bytes(self[2..6].try_into().unwrap())as u64)<<32))as u32,7=>parseuint_arith8le(((u32::from_le_bytes(self[0..4].try_into().unwrap())as u64)<<8)|((u32::from_le_bytes(self[3..7].try_into().unwrap())as u64)<<32))as u32,8=>parseuint_raw8b(self[0..8].try_into().unwrap())as u32,9=>(parseuint_arith1(self[0])as u32)*1_0000_0000+parseuint_raw8b(self[1..9].try_into().unwrap())as u32,_=>(parseuint_arith2le(u16::from_le_bytes(self[0..2].try_into().unwrap()))as u32)*1_0000_0000+(parseuint_raw8b(self[2..10].try_into().unwrap())as u32),}}#[inline(always)]fn parse_u16_raw(&self)->u16{invariant!(self.len()<=5);invariant!(self.iter().all(u8::is_ascii_digit));parseuint_raw7b(&self)as u16}#[inline(always)]fn parse_u8_raw(&self)->u8{invariant!(self.len()<=3);invariant!(self.iter().all(u8::is_ascii_digit));parseuint_raw3b(&self)as u8}#[inline(always)]fn parse_i128_raw(&self)->i128{invariant!(!self.is_empty());if self.is_empty(){0}else if self[0]==b'-'{(&self[1..]).parse_u128_raw().wrapping_neg()as i128}else{self.parse_u128_raw()as i128}}#[inline(always)]fn parse_i64_raw(&self)->i64{invariant!(!self.is_empty());if self.is_empty(){0}else if self[0]==b'-'{(&self[1..]).parse_u64_raw().wrapping_neg()as i64}else{self.parse_u64_raw()as i64}}#[inline(always)]fn parse_i32_raw(&self)->i32{invariant!(!self.is_empty());if self.is_empty(){0}else if self[0]==b'-'{(&self[1..]).parse_u32_raw().wrapping_neg()as i32}else{self.parse_u32_raw()as i32}}#[inline(always)]fn parse_i16_raw(&self)->i16{invariant!(!self.is_empty());if self.is_empty(){0}else if self[0]==b'-'{(&self[1..]).parse_u16_raw().wrapping_neg()as i16}else{self.parse_u16_raw()as i16}}#[inline(always)]fn parse_i8_raw(&self)->i8{invariant!(!self.is_empty());if self.is_empty(){0}else if self[0]==b'-'{(&self[1..]).parse_u128_raw().wrapping_neg()as i8}else{self.parse_u128_raw()as i8}}}pub trait ProconParse{fn get_ascii_byte(&mut self)->u8{self.get_ascii_byte_opt().unwrap()}fn get_ascii_byte_or_default(&mut self)->u8{self.get_ascii_byte_opt().unwrap_or_default()}fn get_ascii_byte_opt(&mut self)->Option<u8>;fn parse_uint<U:UPrimInt>(&mut self)->U{self.parse_uint_opt().unwrap()}fn parse_uint_or_default<U:UPrimInt>(&mut self)->U{self.parse_uint_opt().unwrap_or_default()}fn parse_uint_opt<U:UPrimInt>(&mut self)->Option<U>;fn parse_iint<I:IPrimInt>(&mut self)->I{self.parse_iint_opt().unwrap()}fn parse_iint_or_default<I:IPrimInt>(&mut self)->I{self.parse_iint_opt().unwrap_or_default()}fn parse_iint_opt<I:IPrimInt>(&mut self)->Option<I>;}impl<T:Iterator<Item=u8>>ProconParse for T{fn get_ascii_byte_opt(&mut self)->Option<u8>{loop{match self.next(){Some(c@0x21..=0x7e)=>{return Some(c);}Some(_)=>continue,_=>return None,}}}fn parse_uint_opt<U:UPrimInt>(&mut self)->Option<U>{loop{match self.next(){Some(c@b'0'..=b'9')=>{let mut v=U::from(c-b'0');while let Some(c@b'0'..=b'9')=self.next(){v=v*U::from(10)+U::from(c-b'0');}return Some(v);}Some(_)=>continue,_=>return None,}}}fn parse_iint_opt<I:IPrimInt>(&mut self)->Option<I>{loop{match self.next(){Some(c@b'0'..=b'9')=>{let mut v=I::from((c-b'0')as i8);while let Some(c@b'0'..=b'9')=self.next(){v=v*I::from(10)+I::from((c-b'0')as i8);}return Some(v);}Some(b'-')=>match self.next(){Some(c@b'0'..=b'9')=>{let mut v=I::from(-((c-b'0')as i8));while let Some(c@b'0'..=b'9')=self.next(){v=v*I::from(10)-I::from((c-b'0')as i8);}return Some(v);}_=>return None,},Some(_)=>continue,_=>return None,}}}}impl<R:std::io::BufRead>Drop for ProconIBufIter<R>{fn drop(&mut self){self.inner.consume(unsafe{ptr_offset_u8(self.ptr,self.raw)});}}#[cfg(target_os="linux")]pub fn print(s:&[u8]){unsafe{write(1,s.as_ptr(),s.len())};}#[cfg(target_os="linux")]pub fn print_err(s:&[u8]){unsafe{write(2,s.as_ptr(),s.len())};}#[cfg(target_os="linux")]#[link(name="c")]#[rustfmt::skip]extern "C"{pub fn mmap(addr:*mut u8,length:usize,prot:i32,flags:i32,fd:i32,off:isize)->*mut u8;pub fn munmap(addr:*mut u8,length:usize)->i32;pub fn read(fd:i32,buf:*mut u8,len:usize)->usize;pub fn write(fd:i32,s:*const u8,len:usize);}}
        pub mod invariant {pub use crate::__cargo_equip::macros::invariant::*;#[macro_export]macro_rules!__cargo_equip_macro_def_invariant_invariant{($expr:expr)=>{debug_assert!($expr);if!($expr){#[allow(unused_unsafe)]unsafe{core::hint::unreachable_unchecked()};}};}macro_rules!invariant{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_invariant_invariant!{$($tt)*})}}
        pub mod primint {use std::ops;pub trait UPrimInt:Copy+Default+std::cmp::Ord+ops::Add<Output=Self>+ops::Sub<Output=Self>+ops::Mul<Output=Self>+ops::Div<Output=Self>+ops::Rem<Output=Self>+ops::AddAssign+ops::SubAssign+ops::MulAssign+ops::DivAssign+ops::RemAssign+ops::Shl<u32,Output=Self>+ops::Shr<u32,Output=Self>+ops::ShlAssign<u32>+ops::ShrAssign<u32>+ops::BitAnd<Output=Self>+ops::BitOr<Output=Self>+ops::BitXor<Output=Self>+ops::BitAndAssign+ops::BitOrAssign+ops::BitXorAssign+std::convert::From<u8>{const BITS:u32;fn count_zeros(self)->u32;fn trailing_zeros(self)->u32;fn leading_zeros(self)->u32;fn zero()->Self;fn one()->Self;fn is_zero(self)->bool;fn as_u8(self)->u8;fn as_u16(self)->u16;fn as_u32(self)->u32;fn as_u64(self)->u64;fn as_u128(self)->u128;fn as_usize(self)->usize;fn from_u32(x:u32)->Self;fn from_u64(x:u64)->Self;fn from_u128(x:u128)->Self;fn from_usize(x:usize)->Self;}macro_rules!impl_uprimint{($t:ty)=>{impl UPrimInt for$t{const BITS:u32=(0 as$t).count_zeros();fn count_zeros(self)->u32{self.count_zeros()}fn trailing_zeros(self)->u32{self.trailing_zeros()}fn leading_zeros(self)->u32{self.leading_zeros()}fn zero()->$t{0 as$t}fn one()->$t{1 as$t}fn is_zero(self)->bool{self==(0 as$t)}fn as_u8(self)->u8{self as u8}fn as_u16(self)->u16{self as u16}fn as_u32(self)->u32{self as u32}fn as_u64(self)->u64{self as u64}fn as_u128(self)->u128{self as u128}fn as_usize(self)->usize{self as usize}fn from_u32(x:u32)->Self{x as Self}fn from_u64(x:u64)->Self{x as Self}fn from_u128(x:u128)->Self{x as Self}fn from_usize(x:usize)->Self{x as Self}}};}impl_uprimint!(u8);impl_uprimint!(u16);impl_uprimint!(u32);impl_uprimint!(u64);impl_uprimint!(u128);impl_uprimint!(usize);pub trait IPrimInt:Copy+Default+std::cmp::Ord+ops::Add<Output=Self>+ops::Sub<Output=Self>+ops::Neg<Output=Self>+ops::Mul<Output=Self>+ops::Div<Output=Self>+ops::Rem<Output=Self>+std::convert::From<i8>{const BITS:u32;fn zero()->Self;fn one()->Self;fn is_zero(self)->bool;}macro_rules!impl_iprimint{($t:ty)=>{impl IPrimInt for$t{const BITS:u32=(0 as$t).count_zeros();fn zero()->$t{0 as$t}fn one()->$t{1 as$t}fn is_zero(self)->bool{self==(0 as$t)}}};}impl_iprimint!(i8);impl_iprimint!(i16);impl_iprimint!(i32);impl_iprimint!(i64);impl_iprimint!(i128);impl_iprimint!(isize);}
        pub mod bpsw {use crate::__cargo_equip::preludes::bpsw::*;use primint::UPrimInt;use crate::__cargo_equip::crates::{issq::*,jacobi::*,modint32dynamic::*,montodd::*};pub trait PrimeTest<U>{fn primetest_base2(&self)->bool;fn primetest_miller(&self,base:U)->bool;fn primetest_lucas(&self)->bool;fn primetest_bpsw(&self)->bool;}pub fn lucas_dprobe<U:UPrimInt>(n:U)->Option<i32>{for d in(5u32..).step_by(2){match if(n&U::from(3))==U::from(3)&&(d&3)==3{-jacobi(U::from_u32(d),n)}else{jacobi(U::from_u32(d),n)}{-1=>{return Some(if(d&2)==0{d as i32}else{-(d as i32)});}0=>{if U::from_u32(d)<n{return None;}}_=>{}}if d==61&&issq_u64(n.as_u64()){return None;}}None}macro_rules!trait_primetest{($jacobi:ident,$issq:ident,$u:ty,$i:ty,$w:literal)=>{impl PrimeTest<$u>for Mont<$u>{fn primetest_base2(&self)->bool{let(r,rn,d,k)=(self.r(),self.rn(),self.d(),self.k());let mut br=self.pow(self.add(r,r),d);if br==r||br==rn{return true;}for _ in 1..k{br=self.mrmul(br,br);if br==rn{return true;}}false}fn primetest_miller(&self,mut base:$u)->bool{let(n,r,rn,d,k)=(self.n(),self.r(),self.rn(),self.d(),self.k());if base>=n{base=self.modn(base);if base==0{return true;}}let mut tr=self.pow(self.ar(base),d);if tr==r||tr==rn{return true;}for _ in 1..k{tr=self.mrmul(tr,tr);if tr==rn{return true;}}false}fn primetest_lucas(&self)->bool{let n=self.n();let d=match lucas_dprobe(n){Some(d)=>d,None=>return false,};let qm=self.ar(self.modn(if d<0{((1-d)as$u)/4}else{n-((d-1)as$u)/4}));let mut k=(n+1)<<(n+1).leading_zeros();let mut um=self.r();let mut vm=self.r();let mut qn=qm;let dm=self.ar(if d<0{n-self.modn((-d)as$u)}else{self.modn(d as$u)});k<<=1;while k!=0{um=self.mrmul(um,vm);vm=self.sub(self.mrmul(vm,vm),self.add(qn,qn));qn=self.mrmul(qn,qn);if(k>>($w-1))!=0{let uu=self.div2(self.add(um,vm));vm=self.div2(self.add(self.mrmul(dm,um),vm));um=uu;qn=self.mrmul(qn,qm);}k<<=1;}if um==0||vm==0{return true;}let mut x=(n+1)&(!n);x>>=1;while x!=0{um=self.mrmul(um,vm);vm=self.sub(self.mrmul(vm,vm),self.add(qn,qn));if vm==0{return true;}qn=self.mrmul(qn,qn);x>>=1;}false}fn primetest_bpsw(&self)->bool{self.primetest_base2()&&self.primetest_lucas()}}};}trait_primetest!(jacobi_i64,issq_u64,u64,i64,64);trait_primetest!(jacobi_i32,issq_u32,u32,i32,32);impl PrimeTest<u32>for ModIntDyn{fn primetest_base2(&self)->bool{debug_assert_eq!(self.modulus()%2,1);let n=self.modulus();let n1=n-1;let k=n1.trailing_zeros();let d=n1>>k;let mut t=self.pow(2,d);if t==1||t==n1{return true;}for _ in 1..k{t=self.mul(t,t);if t==n1{return true;}}false}fn primetest_miller(&self,mut base:u32)->bool{debug_assert_eq!(self.modulus()%2,1);let n=self.modulus();let n1=n-1;let k=n1.trailing_zeros();let d=n1>>k;if base>=n{base%=n;if base==0{return true;}}let mut t=self.pow(base,d);if t==1||t==n1{return true;}for _ in 1..k{t=self.mul(t,t);if t==n1{return true;}}false}fn primetest_lucas(&self)->bool{let n=self.modulus();let d=match lucas_dprobe(n){Some(d)=>d,None=>return false,};let q=self.norm(if d<0{((1-d)as u32)/4}else{n-((d-1)as u32)/4});let mut k=(n+1)<<(n+1).leading_zeros();let mut u=1;let mut v=1;let mut qn=q;let du=if d<0{n-self.norm((-d)as u32)}else{self.norm(d as u32)};k<<=1;while k!=0{u=self.mul(u,v);v=self.sub(self.mul(v,v),self.add(qn,qn));qn=self.mul(qn,qn);if(k>>(32-1))!=0{let uu=self.div2(self.add(u,v));v=self.div2(self.add(self.mul(du,u),v));u=uu;qn=self.mul(qn,q);}k<<=1;}if u==0||v==0{return true;}let mut x=(n+1)&(!n);x>>=1;while x!=0{u=self.mul(u,v);v=self.sub(self.mul(v,v),self.add(qn,qn));if v==0{return true;}qn=self.mul(qn,qn);x>>=1;}false}fn primetest_bpsw(&self)->bool{self.primetest_base2()&&self.primetest_lucas()}}pub trait MillerU64{const MILLER_U64_1BASES:[u64;1]=[9345883071009581737];const MILLER_U64_2BASES:[u64;2]=[336781006125,9639812373923155];const MILLER_U64_3BASES:[u64;3]=[4230279247111683200,14694767155120705706,16641139526367750375,];const MILLER_U64_4BASES:[u64;4]=[2,141889084524735,1199124725622454117,11096072698276303650,];const MILLER_U64_5BASES:[u64;5]=[2,4130806001517,149795463772692060,186635894390467037,3967304179347715805,];const MILLER_U64_6BASES:[u64;6]=[2,123635709730000,9233062284813009,43835965440333360,761179012939631437,1263739024124850375,];const MILLER_U64_7BASES:[u64;7]=[2,325,9375,28178,450775,9780504,1795265022];fn primetest_miller_1bases(&self)->bool;fn primetest_miller_2bases(&self)->bool;fn primetest_miller_3bases(&self)->bool;fn primetest_miller_4bases(&self)->bool;fn primetest_miller_5bases(&self)->bool;fn primetest_miller_6bases(&self)->bool;fn primetest_miller_7bases(&self)->bool;fn primetest_miller_mbases(&self)->bool;}impl MillerU64 for Mont<u64>{fn primetest_miller_1bases(&self)->bool{debug_assert!(self.n()<341531);Self::MILLER_U64_1BASES.iter().all(|&base|self.primetest_miller(base))}fn primetest_miller_2bases(&self)->bool{debug_assert!(self.n()<1050535501);Self::MILLER_U64_2BASES.iter().all(|&base|self.primetest_miller(base))}fn primetest_miller_3bases(&self)->bool{debug_assert!(self.n()<350269456337);Self::MILLER_U64_3BASES.iter().all(|&base|self.primetest_miller(base))}fn primetest_miller_4bases(&self)->bool{debug_assert!(self.n()<55245642489451);Self::MILLER_U64_4BASES.iter().all(|&base|self.primetest_miller(base))}fn primetest_miller_5bases(&self)->bool{debug_assert!(self.n()<7999252175582851);Self::MILLER_U64_5BASES.iter().all(|&base|self.primetest_miller(base))}fn primetest_miller_6bases(&self)->bool{debug_assert!(self.n()<585226005592931977);Self::MILLER_U64_6BASES.iter().all(|&base|self.primetest_miller(base))}fn primetest_miller_7bases(&self)->bool{Self::MILLER_U64_7BASES.iter().all(|&base|self.primetest_miller(base))}fn primetest_miller_mbases(&self)->bool{match self.n(){0..=341530=>Self::MILLER_U64_1BASES.iter(),0..=1050535500=>Self::MILLER_U64_2BASES.iter(),0..=350269456336=>Self::MILLER_U64_3BASES.iter(),0..=55245642489450=>Self::MILLER_U64_4BASES.iter(),0..=7999252175582850=>Self::MILLER_U64_5BASES.iter(),0..=585226005592931976=>Self::MILLER_U64_6BASES.iter(),_=>Self::MILLER_U64_7BASES.iter(),}.all(|&base|self.primetest_miller(base))}}pub trait MillerU32{const MILLER_U32_1BASES:[u32;1]=[921211727];const MILLER_U32_2BASES:[u32;2]=[1143370,2350307676];const MILLER_U32_3BASES:[u32;3]=[2,7,61];fn primetest_miller_1bases(&self)->bool;fn primetest_miller_2bases(&self)->bool;fn primetest_miller_3bases(&self)->bool;fn primetest_miller_mbases(&self)->bool;}impl MillerU32 for Mont<u32>{fn primetest_miller_1bases(&self)->bool{debug_assert!(self.n()<49141);Self::MILLER_U32_1BASES.iter().all(|&base|self.primetest_miller(base))}fn primetest_miller_2bases(&self)->bool{debug_assert!(self.n()<360018361);Self::MILLER_U32_2BASES.iter().all(|&base|self.primetest_miller(base))}fn primetest_miller_3bases(&self)->bool{Self::MILLER_U32_3BASES.iter().all(|&base|self.primetest_miller(base))}fn primetest_miller_mbases(&self)->bool{match self.n(){0..=49140=>Self::MILLER_U32_1BASES.iter(),0..=360018360=>Self::MILLER_U32_2BASES.iter(),_=>Self::MILLER_U32_3BASES.iter(),}.all(|&base|self.primetest_miller(base))}}pub fn primetest_u64_bpsw(n:u64)->bool{if n==2{return true;}if n==1||(n&1)==0{return false;}let mont=Mont::<u64>::new(n);mont.primetest_bpsw()}pub fn primetest_u32_bpsw(n:u32)->bool{if n==2{return true;}if n==1||(n&1)==0{return false;}let mont=Mont::<u32>::new(n);mont.primetest_bpsw()}pub fn primetest_u64_miller_mbases(n:u64)->bool{if n==2{return true;}if n==1||(n&1)==0{return false;}let mont=Mont::<u64>::new(n);mont.primetest_miller_mbases()}pub fn primetest_u32_miller_mbases(n:u32)->bool{if n==2{return true;}if n==1||(n&1)==0{return false;}let mont=Mont::<u32>::new(n);mont.primetest_miller_mbases()}impl MillerU32 for ModIntDyn{fn primetest_miller_1bases(&self)->bool{debug_assert!(self.modulus()<49141);Self::MILLER_U32_1BASES.iter().all(|&base|self.primetest_miller(base))}fn primetest_miller_2bases(&self)->bool{debug_assert!(self.modulus()<360018361);Self::MILLER_U32_2BASES.iter().all(|&base|self.primetest_miller(base))}fn primetest_miller_3bases(&self)->bool{Self::MILLER_U32_3BASES.iter().all(|&base|self.primetest_miller(base))}fn primetest_miller_mbases(&self)->bool{match self.modulus(){0..=49140=>Self::MILLER_U32_1BASES.iter(),0..=360018360=>Self::MILLER_U32_2BASES.iter(),_=>Self::MILLER_U32_3BASES.iter(),}.all(|&base|self.primetest_miller(base))}}}
    }

    pub(crate) mod macros {
        pub mod issq {}
        pub mod jacobi {}
        pub mod modint32dynamic {}
        pub mod montodd {}
        pub mod sqrt {}
        pub mod input {pub use crate::{__cargo_equip_macro_def_input_input_inner as input_inner,__cargo_equip_macro_def_input_read_value as read_value};}
        pub mod invariant {pub use crate::__cargo_equip_macro_def_invariant_invariant as invariant;}
        pub mod primint {}
        pub mod bpsw {}
    }

    pub(crate) mod prelude {pub use crate::__cargo_equip::crates::*;}

    mod preludes {
        pub mod issq {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::{invariant,primint,sqrt};}
        pub mod jacobi {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::{invariant,primint};}
        pub mod modint32dynamic {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::invariant;}
        pub mod montodd {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::invariant;}
        pub mod sqrt {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::{invariant,primint};}
        pub mod input {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::{invariant,primint};}
        pub mod invariant {}
        pub mod primint {}
        pub mod bpsw {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::{invariant,issq,jacobi,modint32dynamic,montodd,primint};}
    }
}
yukicoder

結果

テストケース

ソースコード
