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

提出ソース
結果

問題	No.3030 ミラー・ラビン素数判定法のテスト
ユーザー	👑 Mizar
提出日時	2023-05-18 18:27:32
言語	Rust (1.77.0 + proconio)
結果	AC
実行時間	15 ms / 9,973 ms
コード長	48,760 bytes
コンパイル時間	15,425 ms
コンパイル使用メモリ	394,840 KB
実行使用メモリ	5,248 KB
最終ジャッジ日時	2024-12-16 07:52:37
合計ジャッジ時間	15,024 ms
ジャッジサーバーID （参考情報）	judge4 / judge3
このコードへのチャレンジ
（要ログイン）
テストケース

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

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

use crate::__cargo_equip::crates::{bpsw::*, obuf::*, parseint::*};
use std::io::prelude::*;

pub fn solve<B: BufRead>(mut lines: std::io::Lines<B>) {
    // Initialize.
    #[rustfmt::skip] #[cfg(tcheck)] let tins = std::time::Instant::now();
    #[rustfmt::skip] #[cfg(tcheck)] let mut durs = Vec::with_capacity(16);
    let mut obuf = ProconWriteBuffer::with_capacity(1 << 26);
    let mut out = std::io::stdout();
    #[rustfmt::skip] #[cfg(tcheck)] durs.push((tins.elapsed(), "initial"));

    let n = lines.next().unwrap().unwrap().as_bytes().parse_u64_raw() as usize;
    let mut it = lines.take(n).enumerate();
    while let Some((i, Ok(xt))) = it.next() {
        obuf.bytes(xt.as_bytes());
        let x = xt.as_bytes().parse_u64_raw();
        let isprime = primetest_u64_bpsw(x);
        obuf.bytes(if isprime { b" 1\n" } else { b" 0\n" });
        if (i & 511) == 0 {
            obuf.write_all(&mut out);
        }
    }

    #[rustfmt::skip] #[cfg(tcheck)] durs.push((tins.elapsed(), "solve"));
    obuf.write_all(&mut out);
    #[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() {
    solve(stdin().lock().lines());
}
#[cfg(target_os = "linux")]
fn launch() {
    use std::os::unix::io::FromRawFd;
    match unsafe { std::fs::File::from_raw_fd(0) }.metadata() {
        Ok(metadata) if metadata.is_file() => {
            let filelen = metadata.len();
            let input = unsafe { mmap(std::ptr::null_mut(), filelen as usize, 1, 2, 0, 0) };
            solve(unsafe { std::slice::from_raw_parts(input, filelen as usize) }.lines());
        }
        _ => {
            solve(std::io::stdin().lock().lines());
        }
    }
}

#[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;
}

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 https://github.com/mizar/competitive-library-rs licensed under `CC0-1.0` as `crate::__cargo_equip::crates::issq`
///  - `mizar-competitive-integer-jacobi 0.0.0 (path+████████████████████████████████████████████████████████████████████████████)`   published in https://github.com/mizar/competitive-library-rs licensed under `CC0-1.0` as `crate::__cargo_equip::crates::jacobi`
///  - `mizar-competitive-integer-montodd 0.0.0 (path+█████████████████████████████████████████████████████████████████████████████)` published in https://github.com/mizar/competitive-library-rs licensed under `CC0-1.0` as `crate::__cargo_equip::crates::montodd`
///  - `mizar-competitive-integer-sqrt 0.0.0 (path+██████████████████████████████████████████████████████████████████████████)`       published in https://github.com/mizar/competitive-library-rs licensed under `CC0-1.0` as `crate::__cargo_equip::crates::sqrt`
///  - `mizar-competitive-io-obuf 0.0.0 (path+█████████████████████████████████████████████████████████████████████)`                 published in https://github.com/mizar/competitive-library-rs licensed under `CC0-1.0` as `crate::__cargo_equip::crates::obuf`
///  - `mizar-competitive-misc-dec4le 0.0.0 (path+█████████████████████████████████████████████████████████████████████████)`         published in https://github.com/mizar/competitive-library-rs licensed under `CC0-1.0` as `crate::__cargo_equip::crates::dec4le`
///  - `mizar-competitive-misc-invariant 0.0.0 (path+████████████████████████████████████████████████████████████████████████████)`   published in https://github.com/mizar/competitive-library-rs licensed under `CC0-1.0` as `crate::__cargo_equip::crates::invariant`
///  - `mizar-competitive-misc-parseint 0.0.0 (path+███████████████████████████████████████████████████████████████████████████)`     published in https://github.com/mizar/competitive-library-rs licensed under `CC0-1.0` as `crate::__cargo_equip::crates::parseint`
///  - `mizar-competitive-misc-primint 0.0.0 (path+██████████████████████████████████████████████████████████████████████████)`       published in https://github.com/mizar/competitive-library-rs licensed under `CC0-1.0` as `crate::__cargo_equip::crates::primint`
///  - `mizar-competitive-prime-bpsw 0.0.0 (path+████████████████████████████████████████████████████████████████████████)`           published in https://github.com/mizar/competitive-library-rs licensed under `CC0-1.0` 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::*;macro_rules!fn_isqrt_n{($sqrt_newton:ident,$sqrt_exact:ident,$issq_newton:ident,$issq_mod32:ident,$issq_mod48: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_mod4095,issq_u64,u64,32);fn_isqrt_n!(sqrt_floor,isqrt_32_exact,issq_u32_newton,issq_u32_mod32,issq_u32_mod48,issq_u32_mod4095,issq_u32,u32,16);}
        pub mod jacobi {use crate::__cargo_equip::preludes::jacobi::*;use crate::__cargo_equip::crates::{invariant::*,primint::*};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 montodd {use crate::__cargo_equip::preludes::montodd::*;use crate::__cargo_equip::crates::invariant::*;pub trait MontVal<T,BitCountType=u32>{fn m(&self)->T;fn mi(&self)->T;fn mh(&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_modulus(n:T)->Self;}pub struct Mont<T,BitCountType=u32>{m:T,mi:T,mh: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 m(&self)->$x{self.m}fn mi(&self)->$x{self.mi}fn mh(&self)->$x{self.mh}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.m());debug_assert!(b<self.m());let(t,f)=a.overflowing_sub(self.m().wrapping_sub(b));t.wrapping_add((f as$y).wrapping_neg()&self.m())}fn sub(&self,a:$y,b:$y)->$y{debug_assert!(a<self.m());debug_assert!(b<self.m());let(t,f)=a.overflowing_sub(b);t.wrapping_add((f as$y).wrapping_neg()&self.m())}fn div2(&self,ar:$y)->$y{debug_assert!(ar<self.m());let t=ar>>1;t.wrapping_add((((ar&1)!=0)as$y).wrapping_neg()&self.mh())}fn mrmul(&self,ar:$y,br:$y)->$y{debug_assert!(ar<self.m());debug_assert!(br<self.m());let(n,ni)=(self.m(),self.mi());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.m());let(n,ni)=(self.m(),self.mi());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.m());self.mrmul(a,self.r2())}fn pow(&self,mut ar:$y,mut b:$y)->$y{debug_assert!(ar<self.m());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.m(){x}else{x%self.m()}}}};}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_modulus(m:$x)->Self{debug_assert!(m>1&&(m&1)==1);let mi={let bits=(!(0 as$x)).count_ones();let mut x=m.wrapping_mul(3)^2;let mut y=(1 as$x).wrapping_sub(m.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!(m.wrapping_mul(mi),1);let mh=(m>>1)+1;invariant!(m!=0);let(r,r2)=((((1 as$x).wrapping_neg()%m).wrapping_add(1)),((((1 as$x2).wrapping_neg()%(m as$x2))as$x).wrapping_add(1)),);let rn=m-r;let mut d=m-1;let k=d.trailing_zeros();d>>=k;debug_assert_eq!(Self{m,mi,mh,r,rn,r2,d,k}.mr(r),1);debug_assert_eq!(Self{m,mi,mh,r,rn,r2,d,k}.mrmul(1,r2),r);Self{m,mi,mh,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 crate::__cargo_equip::crates::{invariant::*,primint::*};pub fn sqrt_floor<U:UPrimInt>(x:U)->U{if x<=U::one(){return x;}if U::BITS>32&&x<=U::from_u32(!0u32){U::from_u32(sqrt_floor(x.as_u32()))}else if U::BITS<=32||x>U::from_u64(!0u64){let y=(x-U::one()).leading_zeros();let log2=U::BITS-1-y;let k=(U::BITS>>1)-(y>>1);let mut s=U::one()<<k;let mut t=(s+(x>>k))>>1;for _ in 0..match log2{0..=3=>0,4..=9=>1,10..=22=>2,23..=47=>3,48..=98=>4,99..=199=>5,_=>32,}{if t>=s{return s;}s=t;invariant!(!s.is_zero());t=(s+x/s)>>1;}match t.checked_mul(t){Some(u)if u<=x=>t,_=>t-U::one(),}}else{use std::cmp::Ordering::*;let x=x.as_u64();match x{0..=0xfffffffc00000003=>{}0xfffffffc00000004..=0xfffffffe00000000=>return U::from_u32((!0u32)-1),0xfffffffe00000001..=0xffffffffffffffff=>return U::from_u32(!0u32),}let mut s=(x as f64).sqrt()as u64;U::from_u64(match((s+1)*(s+1)).cmp(&x){Less=>loop{s+=1;match((s+1)*(s+1)).cmp(&x){Less=>{}Equal=>break s+1,Greater=>break s,}},Equal=>s+1,Greater=>{while s*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 obuf {use crate::__cargo_equip::preludes::obuf::*;pub use crate::__cargo_equip::crates::{dec4le::*,primint::*};pub struct ProconWriteBuffer(*mut u8,Vec<u8>,Dec4le);impl ProconWriteBuffer{pub fn with_capacity(capacity:usize)->Self{let mut b=Vec::<u8>::with_capacity(capacity);let ptr=b.as_mut_ptr();Self(ptr,b,Dec4le::new())}pub fn get_mut_ptr(&self)->*mut u8{self.0}pub fn set_mut_ptr(&mut self,p:*mut u8){self.0=p;}fn decision(&mut self){let bptr=self.1.as_mut_ptr();unsafe{self.1.set_len((self.0 as usize)-(bptr as usize))};}pub fn clear(&mut self){self.1.clear();self.0=self.1.as_mut_ptr();}pub fn get_slice(&mut self)->&[u8]{self.decision();self.1.as_slice()}pub fn reserve(&mut self,additional:usize){self.decision();self.1.reserve(additional);self.0=self.1.as_mut_ptr();}pub fn reserve_exact(&mut self,additional:usize){self.decision();self.1.reserve_exact(additional);self.0=self.1.as_mut_ptr();}pub fn uint<U>(&mut self,d:U)where U:UPrimInt+std::convert::Into<u128>,{match U::BITS{0..=64=>unsafe{self.2.rawbytes_u64(&mut self.0,Into::<u128>::into(d)as u64)},_=>unsafe{self.2.rawbytes_u128(&mut self.0,Into::<u128>::into(d))},}}pub fn uint_spraw<U>(&mut self,d:U)where U:UPrimInt+std::convert::Into<u128>,{match U::BITS{0..=64=>unsafe{self.2.rawbytes_u64(&mut self.0,Into::<u128>::into(d)as u64);self.sp();},_=>unsafe{self.2.rawbytes_u128(&mut self.0,Into::<u128>::into(d));self.sp();},}}pub fn uint_sp<U>(&mut self,s:&[U])where U:UPrimInt+std::convert::Into<u128>,{if s.is_empty(){return;}let mut p=self.0;for&d in s.iter(){match U::BITS{0..=64=>unsafe{self.2.rawbytes_u64(&mut p,Into::<u128>::into(d)as u64);self.sp();},_=>unsafe{self.2.rawbytes_u128(&mut p,Into::<u128>::into(d));self.sp();},}}self.0=unsafe{p.sub(1)};}pub fn uint_splf<U>(&mut self,s:&[U])where U:UPrimInt+std::convert::Into<u128>,{if s.is_empty(){proconwritebuf_lf(&mut self.0);return;}let mut p=self.0;for&d in s.iter(){match U::BITS{0..=64=>unsafe{self.2.rawbytes_u64(&mut p,Into::<u128>::into(d)as u64);self.sp();},_=>unsafe{self.2.rawbytes_u128(&mut p,Into::<u128>::into(d));self.sp()},}}unsafe{*p.sub(1)=b'\n'};self.0=p;}pub fn usize(&mut self,d:usize){unsafe{self.2.rawbytes_u64(&mut self.0,d as u64)};}pub fn usize_spraw(&mut self,d:usize){unsafe{self.2.rawbytes_u64(&mut self.0,d as u64);self.sp();}}pub fn usize_sp(&mut self,s:&[usize]){if s.is_empty(){return;}let mut p=self.0;for&d in s.iter(){unsafe{self.2.rawbytes_u64(&mut p,d as u64);self.sp();}}self.0=unsafe{p.sub(1)};}pub fn usize_splf(&mut self,s:&[usize]){if s.is_empty(){proconwritebuf_lf(&mut self.0);return;}let mut p=self.0;for&d in s.iter(){unsafe{self.2.rawbytes_u64(&mut p,d as u64);self.sp();}}unsafe{*p.sub(1)=b'\n'};self.0=p;}pub fn iint<I>(&mut self,d:I)where I:IPrimInt+std::convert::Into<i128>,{match I::BITS{0..=64=>unsafe{self.2.rawbytes_i64(&mut self.0,Into::<i128>::into(d)as i64)},_=>unsafe{self.2.rawbytes_i128(&mut self.0,Into::<i128>::into(d))},}}pub fn iint_spraw<I>(&mut self,d:I)where I:IPrimInt+std::convert::Into<i128>,{match I::BITS{0..=64=>unsafe{self.2.rawbytes_i64(&mut self.0,Into::<i128>::into(d)as i64);self.sp();},_=>unsafe{self.2.rawbytes_i128(&mut self.0,Into::<i128>::into(d));self.sp();},}}pub fn iint_sp<I>(&mut self,s:&[I])where I:IPrimInt+std::convert::Into<i128>,{if s.is_empty(){return;}let mut p=self.0;for&d in s.iter(){match I::BITS{0..=64=>unsafe{self.2.rawbytes_i64(&mut p,Into::<i128>::into(d)as i64);self.sp();},_=>unsafe{self.2.rawbytes_i128(&mut p,Into::<i128>::into(d));self.sp();},}}self.0=unsafe{p.sub(1)};}pub fn iint_splf<I>(&mut self,s:&[I])where I:IPrimInt+std::convert::Into<i128>+std::convert::TryInto<u8>,{if s.is_empty(){proconwritebuf_lf(&mut self.0);return;}let mut p=self.0;for&d in s.iter(){match I::BITS{0..=64=>unsafe{self.2.rawbytes_i64(&mut p,Into::<i128>::into(d)as i64);self.sp();},_=>unsafe{self.2.rawbytes_i128(&mut p,Into::<i128>::into(d));self.sp();},}}unsafe{*p.sub(1)=b'\n'};self.0=p;}pub fn bslf(&mut self){unsafe{if self.0!=self.1.as_mut_ptr()&&*(self.0).sub(1)==b' '{*(self.0).sub(1)=b'\n';}else{*(self.0)=b'\n';self.0=self.0.add(1);}}}pub fn sp(&mut self){proconwritebuf_sp(&mut self.0);}pub fn lf(&mut self){proconwritebuf_lf(&mut self.0);}pub fn bytes(&mut self,s:&[u8]){proconwritebuf_bytes(&mut self.0,s);}pub fn str(&mut self,s:&str){proconwritebuf_str(&mut self.0,s);}pub fn string(&mut self,s:&String){proconwritebuf_string(&mut self.0,s);}pub fn yes(&mut self,b:bool){proconwritebuf_bytes(&mut self.0,if b{b"yes"}else{b"no"});}#[allow(non_snake_case)]pub fn Yes(&mut self,b:bool){proconwritebuf_bytes(&mut self.0,if b{b"Yes"}else{b"No"});}#[allow(non_snake_case)]pub fn YES(&mut self,b:bool){proconwritebuf_bytes(&mut self.0,if b{b"YES"}else{b"NO"});}pub fn yes_lf(&mut self,b:bool){proconwritebuf_bytes(&mut self.0,if b{b"yes\n"}else{b"no\n"});}#[allow(non_snake_case)]pub fn Yes_lf(&mut self,b:bool){proconwritebuf_bytes(&mut self.0,if b{b"Yes\n"}else{b"No\n"});}#[allow(non_snake_case)]pub fn YES_lf(&mut self,b:bool){proconwritebuf_bytes(&mut self.0,if b{b"YES\n"}else{b"NO\n"});}pub fn write_all<W>(&mut self,out:&mut W)where W:std::io::Write,{self.decision();let _=out.write_all(self.1.as_slice());self.1.clear();self.0=self.1.as_mut_ptr();}}pub fn proconwritebuf_sp(p:&mut*mut u8){*p=unsafe{**p=b' ';(*p).add(1)}}pub fn proconwritebuf_lf(p:&mut*mut u8){*p=unsafe{**p=b'\n';(*p).add(1)}}pub fn proconwritebuf_bytes(p:&mut*mut u8,bytes:&[u8]){*p=unsafe{let len=bytes.len();std::ptr::copy_nonoverlapping(bytes.as_ptr(),*p,len);(*p).add(len)};}pub fn proconwritebuf_str(p:&mut*mut u8,s:&str){*p=unsafe{let len=s.len();std::ptr::copy_nonoverlapping(s.as_ptr(),*p,len);(*p).add(len)};}pub fn proconwritebuf_string(p:&mut*mut u8,s:&String){*p=unsafe{let len=s.len();std::ptr::copy_nonoverlapping(s.as_ptr(),*p,len);(*p).add(len)};}}
        pub mod dec4le {use crate::__cargo_equip::preludes::dec4le::*;use crate::__cargo_equip::crates::invariant::*;pub struct Dec4le((),(),(),[u32;1000],[u32;10000]);impl Dec4le{pub fn new()->Self{let(mut d3,mut i)=([0u32;1000],0);while i<1000{let(dh,dl)=(i/100,i%100);d3[i as usize]=((dl%10)<<16)|((dl/10)<<8)|dh|0x2030_3030;i+=1;}let(mut d4,mut i)=([0u32;10000],0);while i<1_0000{let(dh,dl)=(i/100,i%100);d4[i as usize]=0x30303030|(dh/10)|((dh%10)<<8)|((dl/10)<<16)|((dl%10)<<24);i+=1;}Self((),(),(),d3,d4)}#[inline(always)]unsafe fn rawbytes_d1(&self,v:&mut*mut u8,x:u32){invariant!(x<10);**v=b'0'|x as u8;*v=v.add(1);}#[inline(always)]unsafe fn rawbytes_d2(&self,v:&mut*mut u8,x:u32){invariant!(x<100);let s=(((x*103>>10)*246+x)as u16|0x3030).to_be_bytes();v.copy_from_nonoverlapping(s.as_ptr(),2);*v=v.add(2);}#[inline(always)]unsafe fn rawbytes_d3(&self,v:&mut*mut u8,x:u32){invariant!(x<1000);v.copy_from_nonoverlapping(self.3[x as usize].to_le_bytes().as_ptr(),3);*v=v.add(3);}#[inline(always)]unsafe fn rawbytes_d4(&self,v:&mut*mut u8,x:u32){invariant!(x<1_0000);v.copy_from_nonoverlapping(self.4[x as usize].to_le_bytes().as_ptr(),4);*v=v.add(4);}#[inline(always)]unsafe fn rawbytes_d5(&self,v:&mut*mut u8,x:u32){invariant!(x<10_0000);let(y0,y1)=(x/10,x%10);v.copy_from_nonoverlapping((((y1 as u64)<<32)|(self.4[y0 as usize]as u64)|0x0030_0000_0000).to_le_bytes().as_ptr(),5,);*v=v.add(5);}#[inline(always)]unsafe fn rawbytes_d6(&self,v:&mut*mut u8,x:u32){invariant!(x<100_0000);let(y0,y1)=(x/100,x%100);v.copy_from_nonoverlapping((((((((y1*103>>10)*246+y1)as u16|0x3030).rotate_right(8))as u64)<<32)|(self.4[y0 as usize]as u64)).to_le_bytes().as_ptr(),6,);*v=v.add(6);}#[inline(always)]unsafe fn rawbytes_d7(&self,v:&mut*mut u8,x:u32){invariant!(x<1000_0000);let(y0,y1)=(x/1000,x%1000);v.copy_from_nonoverlapping((((self.3[y1 as usize]as u64)<<32)|(self.4[y0 as usize]as u64)).to_le_bytes().as_ptr(),7,);*v=v.add(7);}#[inline(always)]unsafe fn rawbytes_d8(&self,v:&mut*mut u8,x:u32){invariant!(x<1_0000_0000);let(y0,y1)=(x/1_0000,x%1_0000);v.copy_from_nonoverlapping((((self.4[y1 as usize]as u64)<<32)|(self.4[y0 as usize]as u64)).to_le_bytes().as_ptr(),8,);*v=v.add(8);}#[inline(always)]unsafe fn rawbytes_d16(&self,v:&mut*mut u8,x:u64){invariant!(x<1_0000_0000_0000_0000);let(y0,y1)=((x/1_0000_0000)as u32,(x%1_0000_0000)as u32);let(z0,z1,z2,z3)=(y0/1_0000,y0%1_0000,y1/1_0000,y1%1_0000);invariant!(z0<1_0000&&z1<1_0000&&z2<1_0000&&z3<1_0000);v.copy_from_nonoverlapping((((self.4[z3 as usize]as u128)<<96)|((self.4[z2 as usize]as u128)<<64)|((self.4[z1 as usize]as u128)<<32)|(self.4[z0 as usize]as u128)).to_le_bytes().as_ptr(),16,);*v=v.add(16);}#[inline(always)]pub unsafe fn rawbytes_d8less(&self,v:&mut*mut u8,x:u32){invariant!(x<1_0000_0000);if x<1_0000{if x<100{match x{0..=9=>self.rawbytes_d1(v,x),10..=99=>self.rawbytes_d2(v,x),_=>core::hint::unreachable_unchecked(),}}else{match x{100..=999=>self.rawbytes_d3(v,x),1000..=9999=>self.rawbytes_d4(v,x),_=>core::hint::unreachable_unchecked(),}}}else{if x<100_0000{match x{1_0000..=9_9999=>self.rawbytes_d5(v,x),10_0000..=99_9999=>self.rawbytes_d6(v,x),_=>core::hint::unreachable_unchecked(),}}else{match x{100_0000..=999_9999=>self.rawbytes_d7(v,x),1000_0000..=9999_9999=>self.rawbytes_d8(v,x),_=>core::hint::unreachable_unchecked(),}}}}#[inline(always)]pub unsafe fn rawbytes_u64(&self,v:&mut*mut u8,x:u64){match x{0..=9999_9999=>self.rawbytes_d8less(v,x as u32),1_0000_0000u64..=9999_9999_9999_9999=>{let(z0,z1)=((x/1_0000_0000)as u32,(x%1_0000_0000)as u32);self.rawbytes_d8less(v,z0);self.rawbytes_d8(v,z1);}1_0000_0000_0000_0000..=1844_6744_0737_0955_1615=>{let(y0,y1)=((x/1_0000_0000_0000_0000)as u32,x%1_0000_0000_0000_0000,);invariant!(y0<1845);self.rawbytes_d8less(v,y0);self.rawbytes_d16(v,y1);}}}#[inline(always)]pub unsafe fn rawbytes_u128(&self,v:&mut*mut u8,x:u128){match x{0..=9999_9999=>self.rawbytes_d8less(v,x as u32),1_0000_0000..=9999_9999_9999_9999=>{let(z0,z1)=((x/1_0000_0000)as u32,(x%1_0000_0000)as u32);self.rawbytes_d8less(v,z0);self.rawbytes_d8(v,z1);}1_0000_0000_0000_0000..=1844_6744_0737_0955_1615=>{let(y0,y1)=((x/1_0000_0000_0000_0000)as u32,(x%1_0000_0000_0000_0000)as u64,);invariant!(y0<1845);self.rawbytes_d8less(v,y0);self.rawbytes_d16(v,y1);}1844_6744_0737_0955_1616..=9999_9999_9999_9999_9999_9999=>{let mut y0=((((x>>16)as u64 as u128)*16615349947311448411)>>101)as u32;let mut y1=(x-(y0 as u128)*1_0000_0000_0000_0000)as u64;if let Some(yt)=y1.checked_sub(1_0000_0000_0000_0000){y1=yt;y0+=1;}invariant!(y0<1_0000_0000);invariant!(y1<1_0000_0000_0000_0000);self.rawbytes_d8less(v,y0);self.rawbytes_d16(v,y1);}1_0000_0000_0000_0000_0000_0000..=9999_9999_9999_9999_9999_9999_9999_9999=>{let mut y0=((((x>>43)as u64 as u128)*16615349947311448411)>>74)as u64;let mut y1=(x-(y0 as u128)*1_0000_0000_0000_0000)as u64;if let Some(yt)=y1.checked_sub(1_0000_0000_0000_0000){y1=yt;y0+=1;}invariant!(y0<1_0000_0000_0000_0000);invariant!(y1<1_0000_0000_0000_0000);let(z0,z1)=((y0/1_0000_0000)as u32,(y0%1_0000_0000)as u32);self.rawbytes_d8less(v,z0);self.rawbytes_d8(v,z1);self.rawbytes_d16(v,y1);}1_0000_0000_0000_0000_0000_0000_0000_0000..=340_2823_6692_0938_4634_6337_4607_4317_6821_1455=>{let mut y0=((((x>>64)as u64 as u128)*14965776766268445882)>>106)as u32;let mut y1=x-(y0 as u128)*1_0000_0000_0000_0000_0000_0000_0000_0000;if let Some(yt)=y1.checked_sub(1_0000_0000_0000_0000_0000_0000_0000_0000){y1=yt;y0+=1;}invariant!(y0<340_2824);invariant!(y1<1_0000_0000_0000_0000_0000_0000_0000_0000);let mut z0=((((y1>>43)as u64 as u128)*16615349947311448411)>>74)as u64;let mut z1=(y1-(z0 as u128)*1_0000_0000_0000_0000)as u64;if let Some(zt)=z1.checked_sub(1_0000_0000_0000_0000){z1=zt;z0+=1;}invariant!(z0<1_0000_0000_0000_0000);invariant!(z1<1_0000_0000_0000_0000);self.rawbytes_d8less(v,y0);self.rawbytes_d16(v,z0);self.rawbytes_d16(v,z1);}}}#[inline(always)]pub unsafe fn rawbytes_i64(&self,v:&mut*mut u8,x:i64){let x=if x<0{**v=b'-';*v=v.add(1);x.wrapping_neg()as u64}else{x as u64};self.rawbytes_u64(v,x);}#[inline(always)]pub unsafe fn rawbytes_i128(&self,v:&mut*mut u8,x:i128){let x=if x<0{**v=b'-';*v=v.add(1);x.wrapping_neg()as u128}else{x as u128};self.rawbytes_u128(v,x);}}}
        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 parseint {use crate::__cargo_equip::preludes::parseint::*;use crate::__cargo_equip::crates::invariant::invariant;use std::convert::TryInto;#[inline]pub 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]pub 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]pub 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]pub 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]pub fn parseuint_arith2le(a:u16)->u16{(a&0x0f0f).wrapping_mul((10<<8)+1)>>8}#[inline]pub fn parseuint_arith2be(a:u16)->u16{(a&0x0f0f).wrapping_mul((1<<8)+10)>>8}#[inline(always)]pub fn parseuint_arith1(a:u8)->u8{a&0x0f}#[inline(always)]pub 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)]pub 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)]pub fn parseuint_raw8b(s:[u8;8])->u64{parseuint_arith8le(u64::from_le_bytes(s))}#[inline(always)]pub 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)]pub fn parseuint_raw4b(s:[u8;4])->u32{parseuint_arith4le(u32::from_le_bytes(s))}#[inline(always)]pub 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)]pub fn parseuint_raw2b(s:[u8;2])->u16{parseuint_arith2le(u16::from_le_bytes(s))}#[inline(always)]pub 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]{#[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)}}}#[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()))}}}#[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 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 checked_add(self,rhs:Self)->Option<Self>;fn checked_sub(self,rhs:Self)->Option<Self>;fn checked_mul(self,rhs:Self)->Option<Self>;fn checked_pow(self,exp:u32)->Option<Self>;fn wrapping_add(self,rhs:Self)->Self;fn wrapping_sub(self,rhs:Self)->Self;fn wrapping_neg(self)->Self;fn wrapping_mul(self,rhs:Self)->Self;fn overflowing_add(self,rhs:Self)->(Self,bool);fn overflowing_sub(self,rhs:Self)->(Self,bool);fn overflowing_neg(self)->(Self,bool);fn overflowing_mul(self,rhs:Self)->(Self,bool);fn pow(self,exp:u32)->Self;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 checked_add(self,rhs:$t)->Option<$t>{self.checked_add(rhs)}fn checked_sub(self,rhs:$t)->Option<$t>{self.checked_sub(rhs)}fn checked_mul(self,rhs:$t)->Option<$t>{self.checked_mul(rhs)}fn checked_pow(self,exp:u32)->Option<$t>{self.checked_pow(exp)}fn wrapping_add(self,rhs:$t)->$t{self.wrapping_add(rhs)}fn wrapping_sub(self,rhs:$t)->$t{self.wrapping_sub(rhs)}fn wrapping_neg(self)->$t{self.wrapping_neg()}fn wrapping_mul(self,rhs:$t)->$t{self.wrapping_mul(rhs)}fn overflowing_add(self,rhs:$t)->($t,bool){self.overflowing_add(rhs)}fn overflowing_sub(self,rhs:$t)->($t,bool){self.overflowing_sub(rhs)}fn overflowing_neg(self)->($t,bool){self.overflowing_neg()}fn overflowing_mul(self,rhs:$t)->($t,bool){self.overflowing_mul(rhs)}fn pow(self,exp:u32)->Self{self.pow(exp)}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 crate::__cargo_equip::crates::{issq::*,jacobi::*};pub use crate::__cargo_equip::crates::{montodd::*,primint::*};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(m,r,rn,d,k)=(self.m(),self.r(),self.rn(),self.d(),self.k());if base>=m{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.m();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);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_modulus(n);mont.primetest_bpsw()}}
    }

    pub(crate) mod macros {
        pub mod issq {}
        pub mod jacobi {}
        pub mod montodd {}
        pub mod sqrt {}
        pub mod obuf {}
        pub mod dec4le {}
        pub mod invariant {pub use crate::__cargo_equip_macro_def_invariant_invariant as invariant;}
        pub mod parseint {}
        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 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 obuf {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::{dec4le,invariant,primint};}
        pub mod dec4le {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::invariant;}
        pub mod invariant {}
        pub mod parseint {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::{invariant,primint};}
        pub mod primint {}
        pub mod bpsw {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::{invariant,issq,jacobi,montodd,primint};}
    }
}
yukicoder

結果

テストケース

ソースコード
