#984056 (Rust) No.186 中華風 (Easy)

• 問題: No.186 中華風 (Easy)
• ユーザー: tayu
• 提出日時: 2024-05-30 01:57:19
• 言語: Rust (1.77.0)
• 結果: AC
• 実行時間: 1 ms / 2,000 ms
• コード長: 55,958 bytes
• コンパイル時間: 13,989 ms
• コンパイル使用メモリ: 394,412 KB
• 実行使用メモリ: 6,944 KB
• 最終ジャッジ日時: 2024-05-30 01:57:35
• 合計ジャッジ時間: 13,834 ms
• ジャッジサーバーID （参考情報）: judge5 / judge3

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 6,816 KB
testcase_01	AC	1 ms; 6,816 KB
testcase_02	AC	1 ms; 6,940 KB
testcase_03	AC	1 ms; 6,940 KB
testcase_04	AC	1 ms; 6,940 KB
testcase_05	AC	1 ms; 6,940 KB
testcase_06	AC	1 ms; 6,940 KB
testcase_07	AC	1 ms; 6,940 KB
testcase_08	AC	1 ms; 6,940 KB
testcase_09	AC	1 ms; 6,944 KB
testcase_10	AC	1 ms; 6,940 KB
testcase_11	AC	1 ms; 6,944 KB
testcase_12	AC	1 ms; 6,944 KB
testcase_13	AC	1 ms; 6,940 KB
testcase_14	AC	1 ms; 6,944 KB
testcase_15	AC	1 ms; 6,944 KB
testcase_16	AC	1 ms; 6,944 KB
testcase_17	AC	1 ms; 6,944 KB
testcase_18	AC	1 ms; 6,944 KB
testcase_19	AC	1 ms; 6,944 KB
testcase_20	AC	1 ms; 6,944 KB
testcase_21	AC	1 ms; 6,944 KB
testcase_22	AC	1 ms; 6,940 KB

ソースコード

// https://yukicoder.me/problems/447
pub use __cargo_equip::prelude::*;

use cpio::*;
use math::MathInt;

fn main() {
    scan!(x1: u64, y1: u64, x2: u64, y2: u64, x3: u64, y3: u64);

    if let Some(Some((res, lcm))) = x1.crt(y1, x2, y2).map(|(c, lcm)| c.crt(lcm, x3, y3)) {
        if res == 0 {
            putln!(lcm);
        } else {
            putln!(res);
        }
    } else {
        putln!(-1);
    }
}

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

///  # Bundled libraries
/// 
///  - `arbitrary-montgomery-modint 0.1.0 (path+██████████████████████████████████████████████████████████████████)` published in **missing** licensed under `CC0-1.0` as `crate::__cargo_equip::crates::arbitrary_montgomery_modint`
///  - `cpio 0.1.0 (git+https://github.com/tayu0110/tayu-procon.git#6f2de33953ba448b2b2bb6014dd2ff0dfe38d2ca)`                                licensed under `CC0-1.0` as `crate::__cargo_equip::crates::cpio`
///  - `math 0.1.0 (path+████████████████████████████████████)`                                                      published in **missing** licensed under `CC0-1.0` as `crate::__cargo_equip::crates::math`
///  - `numeric 0.1.0 (path+███████████████████████████████████████)`                                                published in **missing** licensed under `CC0-1.0` as `crate::__cargo_equip::crates::numeric`
///  - `simple-rand 0.1.0 (path+███████████████████████████████████████████)`                                        published in **missing** licensed under `CC0-1.0` as `crate::__cargo_equip::crates::simple_rand`
///  - `zero-one 0.1.0 (path+████████████████████████████████████████████████)`                                      published in **missing** licensed under `CC0-1.0` as `crate::__cargo_equip::crates::__zero_one_0_1_0`
#[cfg_attr(any(), rustfmt::skip)]
#[allow(unused)]
mod __cargo_equip {
    pub(crate) mod crates {
        pub mod arbitrary_montgomery_modint {use std::ops::{Add,AddAssign,Div,DivAssign,Mul,MulAssign,Sub,SubAssign};const fn montgomery_reduction(val:u64,modulo:u64,modulo_inv:u64)->u64{let(t,f)=(((val.wrapping_mul(modulo_inv)as u128).wrapping_mul(modulo as u128)>>64)as u64).overflowing_neg();t.wrapping_add(modulo*f as u64)}const fn montgomery_multiplication(lhs:u64,rhs:u64,modulo:u64,modulo_inv:u64)->u64{let a=lhs as u128*rhs as u128;let(t,f)=((a>>64)as u64).overflowing_sub((((a as u64).wrapping_mul(modulo_inv)as u128).wrapping_mul(modulo as u128)>>64)as u64,);t.wrapping_add(modulo*f as u64)}#[derive(Clone,Copy,PartialEq,Eq,Hash)]pub struct ArbitraryMontgomeryModint{pub val:u64,modulo:u64,modulo_inv:u64,r:u64,r2:u64,}impl ArbitraryMontgomeryModint{#[inline]pub const fn new(val:u64,modulo:u64)->Self{Self::raw(val%modulo,modulo)}pub const fn raw(val:u64,modulo:u64)->Self{if modulo==998244353{let val=montgomery_multiplication(val,299560064,modulo,996491785301655553);return Self{val,modulo,modulo_inv:996491785301655553,r:932051910,r2:299560064,};}let r=((1u128<<64)%modulo as u128)as u64;let r2=((modulo as u128).wrapping_neg()%modulo as u128)as u64;let modulo_inv={let inv=modulo.wrapping_mul(2u64.wrapping_sub(modulo.wrapping_mul(modulo)));let inv=inv.wrapping_mul(2u64.wrapping_sub(modulo.wrapping_mul(inv)));let inv=inv.wrapping_mul(2u64.wrapping_sub(modulo.wrapping_mul(inv)));let inv=inv.wrapping_mul(2u64.wrapping_sub(modulo.wrapping_mul(inv)));inv.wrapping_mul(2u64.wrapping_sub(modulo.wrapping_mul(inv)))};let val=montgomery_multiplication(val,r2,modulo,modulo_inv);Self{val,modulo,modulo_inv,r,r2}}#[inline]const fn from_raw_parts_unchecked(val:u64,modulo:u64,modulo_inv:u64,r:u64,r2:u64,)->Self{Self{val,modulo,modulo_inv,r,r2}}#[inline]pub const fn from_same_mod(val:u64,from:Self)->Self{Self::from_same_mod_unchecked(val%from.modulo,from)}#[inline]pub const fn from_same_mod_unchecked(val:u64,from:Self)->Self{let val=montgomery_multiplication(val,from.r2,from.modulo,from.modulo_inv);Self::from_raw_parts_unchecked(val,from.modulo,from.modulo_inv,from.r,from.r2)}#[inline]pub const fn val(&self)->u64{montgomery_reduction(self.val,self.modulo,self.modulo_inv)}#[inline]pub const fn rawval(&self)->u64{self.val}#[inline]pub const fn one(&self)->Self{Self{val:self.r,modulo:self.modulo,modulo_inv:self.modulo_inv,r:self.r,r2:self.r2,}}#[inline]pub const fn zero(&self)->Self{Self{val:0,modulo:self.modulo,modulo_inv:self.modulo_inv,r:self.r,r2:self.r2,}}pub fn pow(&self,mut n:u64)->Self{let mut val=self.val;let mut res=self.r;while n!=0{if n&1!=0{res=montgomery_multiplication(res,val,self.modulo,self.modulo_inv);}val=montgomery_multiplication(val,val,self.modulo,self.modulo_inv);n>>=1;}Self{val:res,modulo:self.modulo,modulo_inv:self.modulo_inv,r:self.r,r2:self.r2,}}#[inline]pub fn inv(&self)->Self{self.pow(self.modulo-2)}}impl Add for ArbitraryMontgomeryModint{type Output=Self;fn add(self,rhs:Self)->Self::Output{let(t,fa)=self.val.overflowing_add(rhs.val);let(u,fs)=t.overflowing_sub(self.modulo);Self{val:if fa||!fs{u}else{t},modulo:self.modulo,modulo_inv:self.modulo_inv,r:self.r,r2:self.r2,}}}impl Sub for ArbitraryMontgomeryModint{type Output=Self;fn sub(self,rhs:Self)->Self::Output{let(val,f)=self.val.overflowing_sub(rhs.val);Self{val:if f{val.wrapping_add(self.modulo)}else{val},modulo:self.modulo,modulo_inv:self.modulo_inv,r:self.r,r2:self.r2,}}}impl Mul for ArbitraryMontgomeryModint{type Output=Self;fn mul(self,rhs:Self)->Self::Output{Self{val:montgomery_multiplication(self.val,rhs.val,self.modulo,self.modulo_inv),modulo:self.modulo,modulo_inv:self.modulo_inv,r:self.r,r2:self.r2,}}}impl Div for ArbitraryMontgomeryModint{type Output=Self;fn div(self,rhs:Self)->Self::Output{self*rhs.inv()}}impl AddAssign for ArbitraryMontgomeryModint{fn add_assign(&mut self,rhs:Self){*self=*self+rhs;}}impl SubAssign for ArbitraryMontgomeryModint{fn sub_assign(&mut self,rhs:Self){*self=*self-rhs;}}impl MulAssign for ArbitraryMontgomeryModint{fn mul_assign(&mut self,rhs:Self){*self=*self*rhs;}}impl DivAssign for ArbitraryMontgomeryModint{fn div_assign(&mut self,rhs:Self){*self=*self/rhs;}}impl std::fmt::Debug for ArbitraryMontgomeryModint{fn fmt(&self,f:&mut std::fmt::Formatter<'_>)->std::fmt::Result{write!(f,"{}",self.val())}}impl std::fmt::Display for ArbitraryMontgomeryModint{fn fmt(&self,f:&mut std::fmt::Formatter<'_>)->std::fmt::Result{write!(f,"{}",self.val())}}}
        pub mod cpio {pub use crate::__cargo_equip::macros::cpio::*;#[cfg(target_family="unix")]mod ext{use std::os::raw::{c_int,c_long,c_void};extern "C"{pub fn mmap(addr:*mut c_void,len:usize,prot:c_int,flags:c_int,fd:c_int,offset:c_long,)->*mut c_void;}pub const PROT_READ:i32=1;pub const MAP_PRIVATE:i32=2;}mod input{use std::{fs::File,io::Read,str::from_utf8};use crate::__cargo_equip::crates::cpio::parse_number::{parse16c,parse4c,parse8c};#[inline(always)]const fn parse_small_integer(bytes:&[u8],d:usize)->u64{const S:u64=b'0' as u64*11;const T:u64=b'0' as u64*111;debug_assert!(0<d&&d<4);match d{1=>(bytes[0]&15)as u64,2=>bytes[0]as u64*10+bytes[1]as u64-S,3=>bytes[0]as u64*100+bytes[1]as u64*10+bytes[2]as u64-T,_=>unreachable!(),}}pub trait FromBytes{fn from_bytes(bytes:&[u8])->Self;}impl FromBytes for u64{fn from_bytes(bytes:&[u8])->Self{debug_assert!(!bytes.is_empty()&&bytes.len()<=20);const TEN:[u64;4]=[1,10,100,1000];unsafe{match bytes.len(){1=>parse_small_integer(bytes,1),2=>parse_small_integer(bytes,2),3=>parse_small_integer(bytes,3),4=>parse4c(bytes.try_into().unwrap()),8=>parse8c(bytes.try_into().unwrap()),12=>{parse4c(bytes[..4].try_into().unwrap())*100_000_000+parse8c(bytes[4..].try_into().unwrap())}16=>parse16c(bytes),20=>{parse16c(bytes[..16].try_into().unwrap())*10_000+parse4c(bytes[16..].try_into().unwrap())}len=>{let offset=len&!0b11;Self::from_bytes(&bytes[..offset])*TEN[len&0b11]+parse_small_integer(&bytes[offset..],len&0b11)}}}}}macro_rules!impl_unsigned_integer_from_bytes{($($t:ty),*)=>{$(impl FromBytes for$t{fn from_bytes(bytes:&[u8])->Self{<u64 as FromBytes>::from_bytes(bytes)as$t}})*};}impl_unsigned_integer_from_bytes!(u8,u16,u32,usize);impl FromBytes for u128{fn from_bytes(bytes:&[u8])->Self{if bytes.len()>19{const P:u128=10u128.pow(19);let offset=bytes.len()-19;u64::from_bytes(&bytes[..offset])as u128*P+u64::from_bytes(&bytes[offset..])as u128}else{u64::from_bytes(bytes)as u128}}}macro_rules!impl_signed_integer_from_bytes{($($s:ty,$u:ty),*)=>{$(impl FromBytes for$s{fn from_bytes(bytes:&[u8])->Self{debug_assert!(!bytes.is_empty());let sgn=bytes[0]==b'-';let mut res=<$u as FromBytes>::from_bytes(&bytes[sgn as usize..]);debug_assert!(res<=<$s>::MAX as$u+sgn as$u);if sgn{res=res.wrapping_neg();}res as$s}})*};}impl_signed_integer_from_bytes!(i8,u8,i16,u16,i32,u32,i64,u64,isize,usize,i128,u128);impl FromBytes for char{fn from_bytes(bytes:&[u8])->Self{debug_assert!(!bytes.is_empty());let mut it=from_utf8(bytes).expect("Malformed UTF-8 byte sequence").chars();let res=it.next().unwrap();assert!(it.next().is_none(),"Failed to parse `char`: multiple characters");res}}impl FromBytes for String{fn from_bytes(bytes:&[u8])->Self{from_utf8(bytes).expect("Malformed UTF-8 byte sequence").to_owned()}}pub struct Source{buf:Box<[u8]>,_file:Option<File>,head:usize,}impl Source{fn get_buffer_use_std(stdin:&mut impl Read)->Box<[u8]>{let mut buf=Vec::with_capacity(1<<18);stdin.read_to_end(&mut buf).unwrap();buf.resize(buf.len()+32,b' ');buf.into_boxed_slice()}#[cfg(target_family="unix")]pub fn new()->Self{use std::{os::fd::FromRawFd,ptr::{null_mut,slice_from_raw_parts_mut},};use crate::__cargo_equip::crates::cpio::ext::{mmap,MAP_PRIVATE,PROT_READ};let mut stdin=unsafe{File::from_raw_fd(0)};let meta=stdin.metadata().unwrap();let buf=if meta.is_file(){let len=meta.len()as usize;let mapping=unsafe{mmap(null_mut()as _,len,PROT_READ,MAP_PRIVATE,0,0)};let res=slice_from_raw_parts_mut(mapping as*mut u8,len);unsafe{Box::from_raw(res)}}else{Self::get_buffer_use_std(&mut stdin)};Self{buf,_file:Some(stdin),head:0,}}#[cfg(not(target_family="unix"))]pub fn new()->Self{let buf=Self::get_buffer_use_std(&mut std::io::stdin().lock());Self{buf,_file:None,head:0,}}pub fn next_start(&mut self)->Option<usize>{while self.buf.get(self.head)?<=&b' '{self.head+=1;}Some(self.head)}pub fn next_token(&mut self)->&[u8]{let head=self.next_start().expect("There are no more tokens");while self.buf.get(self.head).filter(|&&b|b>b' ').is_some(){self.head+=1;}&self.buf[head..self.head]}}static mut INPUT:*mut Source=0 as*mut Source;static mut STDIN_SOURCE:fn()->&'static mut Source=init;#[cold]fn init()->&'static mut Source{unsafe{INPUT=Box::leak(Box::new(Source::new()));STDIN_SOURCE=||INPUT.as_mut().unwrap_unchecked();STDIN_SOURCE()}}pub fn get_stdin_source()->&'static mut Source{unsafe{STDIN_SOURCE()}}}mod output{use std::{cell::RefCell,io::Write,iter,ptr::{addr_of_mut,write_volatile},};const LUT:[u8;40000]={let mut cnt=0;let mut lut=[0;40000];while cnt<10000{let th=cnt/1000;let hu=cnt/100%10;let te=cnt/10%10;let on=cnt%10;lut[cnt*4]=th as u8+b'0';lut[cnt*4+1]=hu as u8+b'0';lut[cnt*4+2]=te as u8+b'0';lut[cnt*4+3]=on as u8+b'0';cnt+=1;}lut};pub trait Display{fn fmt(&self,buf:&mut Buffer,sep:&str);}#[inline(always)]fn write_small_integer(int:u16,buf:&mut Buffer){debug_assert!(int<10000);let base=int as usize*4;buf.write_unchecked(&LUT[base+3-int.ilog10()as usize..base+4]);}macro_rules!impl_stringify_unsigned_integer{($t:ty$(as$convert:ty)?,$st:ty,$block:literal)=>{impl Display for$t{fn fmt(&self,f:&mut Buffer,_:&str){f.reserve($block*4);let mut now=*self$(as$convert)?;if now==0{f.write_unchecked("0".as_bytes());return;}if now<10000{write_small_integer(now as u16,f);return;}let mut t=[0;$block];let mut cnt=$block;while now>=10000{cnt-=1;(now,t[cnt])=(now/10000,(now%10000)as u16);}write_small_integer(now as u16,f);for&t in&t[cnt..]{let t=t as usize;f.write_unchecked(&LUT[t*4..t*4+4]);}}}impl Display for$st{fn fmt(&self,buf:&mut Buffer,sep:&str){if*self<0{buf.write("-".as_bytes());self.unsigned_abs().fmt(buf,sep);}else{(*self as$t).fmt(buf,sep);}}}};}impl_stringify_unsigned_integer!(u8 as u32,i8,0);impl_stringify_unsigned_integer!(u16 as u32,i16,2);impl_stringify_unsigned_integer!(u32,i32,3);impl_stringify_unsigned_integer!(u64,i64,5);impl_stringify_unsigned_integer!(usize,isize,5);impl_stringify_unsigned_integer!(u128,i128,10);impl Display for char{fn fmt(&self,buf:&mut Buffer,_:&str){let mut b=[0;4];buf.write(self.encode_utf8(&mut b).as_bytes());}}impl Display for str{fn fmt(&self,buf:&mut Buffer,_:&str){buf.write(self.as_bytes());}}impl<T:Display>Display for[T]{fn fmt(&self,buf:&mut Buffer,sep:&str){if let Some(item)=self.first(){item.fmt(buf,sep);for item in self.iter().skip(1){buf.write(sep.as_bytes());item.fmt(buf,sep);}}}}macro_rules!impl_base_ust{($ty:ty,$b:ty,$($t:tt)*)=>{impl<$($t)*>Display for$ty{fn fmt(&self,buf:&mut Buffer,sep:&str){<$b as Display>::fmt(self,buf,sep)}}};}impl_base_ust!(&str,str,);impl_base_ust!(&[T],[T],T:Display);impl_base_ust!([T;N],[T],T:Display,const N:usize);impl_base_ust!(Vec<T>,[T],T:Display);macro_rules!impl_fmt_iterator{($t:ty,$($g:tt)*)=>{impl<$($g)*>Display for$t{fn fmt(&self,buf:&mut Buffer,sep:&str){let mut iter=self.clone();if let Some(item)=iter.next(){item.fmt(buf,sep);for item in iter{buf.write(sep.as_bytes());item.fmt(buf,sep);}}}}};}impl_fmt_iterator!(std::slice::Iter<'_,T>,T:Display);impl_fmt_iterator!(iter::Chain<A,B>,T:Display,A:Clone+Iterator<Item=T>,B:Clone+Iterator<Item=T>);impl_fmt_iterator!(iter::Cloned<I>,'a,T:Display+Clone+'a,I:Clone+Iterator<Item=&'a T>);impl_fmt_iterator!(iter::Copied<I>,'a,T:Display+Clone+Copy+'a,I:Clone+Iterator<Item=&'a T>);impl_fmt_iterator!(iter::Cycle<I>,T:Display,I:Clone+Iterator<Item=T>);impl_fmt_iterator!(iter::Filter<I,P>,T:Display,I:Clone+Iterator<Item=T>,P:Clone+FnMut(&I::Item)->bool);impl_fmt_iterator!(iter::FilterMap<I,F>,T:Display,I:Clone+Iterator,F:Clone+FnMut(I::Item)->Option<T>);impl_fmt_iterator!(iter::Map<I,F>,T:Display,I:Clone+Iterator,F:Clone+FnMut(I::Item)->T);impl_fmt_iterator!(iter::Skip<I>,T:Display,I:Clone+Iterator<Item=T>);impl_fmt_iterator!(iter::StepBy<I>,T:Display,I:Clone+Iterator<Item=T>);impl_fmt_iterator!(iter::Take<I>,T:Display,I:Clone+Iterator<Item=T>);pub struct Buffer{head:usize,buf:[u8;Self::LEN],}impl Buffer{const LEN:usize=1<<20;const fn new()->Self{Self{head:0,buf:[0;Self::LEN],}}fn reserve(&mut self,len:usize){assert!(len<=Self::LEN);if self.head+len>Self::LEN{self.flush();}}fn write_unchecked(&mut self,buf:&[u8]){self.buf[self.head..self.head+buf.len()].copy_from_slice(buf);self.head+=buf.len();}fn write(&mut self,buf:&[u8]){if self.head+buf.len()<=Self::LEN{self.write_unchecked(buf);return;}for c in buf.chunks(Self::LEN){self.flush();self.buf[..c.len()].copy_from_slice(c);self.head=c.len();}}fn flush(&mut self){if self.head>0{std::io::stdout().write_all(&self.buf[..self.head]).ok();self.head=0;}}}struct DumFlush(u32);impl Drop for DumFlush{fn drop(&mut self){get_output().flush();}}thread_local!{static DUMMY:RefCell<DumFlush> =const{RefCell::new(DumFlush(0))};}static mut BUFFER:Buffer=Buffer::new();static mut GET_BUFFER:fn()->&'static mut Buffer=init;#[cold]fn init()->&'static mut Buffer{DUMMY.with(|d|unsafe{write_volatile(addr_of_mut!(d.borrow_mut().0),32)});unsafe{GET_BUFFER=get_output}get_output()}fn get_output()->&'static mut Buffer{unsafe{addr_of_mut!(BUFFER).as_mut().unwrap()}}pub fn get_buffer()->&'static mut Buffer{unsafe{GET_BUFFER()}}}mod parse_number{pub(in crate::__cargo_equip::crates::cpio)unsafe fn parse4c(buf:[u8;4])->u64{let mut chunk=u32::from_le_bytes(buf);chunk-=0x30303030;chunk=(chunk*10+(chunk>>8))&0xff00ff;((chunk*100+(chunk>>16))&0xffff)as u64}pub(in crate::__cargo_equip::crates::cpio)unsafe fn parse8c(buf:[u8;8])->u64{let mut chunk=u64::from_le_bytes(buf);chunk-=0x3030303030303030;chunk=(chunk*10+(chunk>>8))&0xff00ff00ff00ff;chunk=(chunk*100+(chunk>>16))&0xffff0000ffff;(chunk*10000+(chunk>>32))&0xffffffff}#[cfg(not(target_arch="x86_64"))]pub(in crate::__cargo_equip::crates::cpio)unsafe fn parse16c(buf:&[u8])->u64{let buf:[u8;16]=buf.try_into().unwrap();let mut chunk=u128::from_le_bytes(buf);chunk-=0x30303030303030303030303030303030;chunk=(chunk*10+(chunk>>8))&0xff00ff00ff00ff00ff00ff00ff00ff;chunk=(chunk*100+(chunk>>16))&0xffff0000ffff0000ffff0000ffff;chunk=(chunk*10000+(chunk>>32))&0xffffffff00000000ffffffff;((chunk*100000000+(chunk>>64))&0xffffffffffffffff)as u64}#[cfg(target_arch="x86_64")]mod x86_64{use std::arch::x86_64::{__m128i,_mm_cvtsi128_si64,_mm_lddqu_si128,_mm_madd_epi16,_mm_maddubs_epi16,_mm_packus_epi32,_mm_sub_epi8,};use std::mem::transmute;const ZEROS:__m128i=unsafe{transmute([b'0';16])};const TEN:__m128i=unsafe{transmute([[10u8,1u8];8])};const HUN:__m128i=unsafe{transmute([[100u8,0,1,0];4])};const THO:__m128i=unsafe{transmute([16u8,39,1,0,16,39,1,0,0,0,0,0,0,0,0,0])};#[target_feature(enable="sse2",enable="sse3",enable="ssse3",enable="sse4.1")]pub unsafe fn parse16c(buf:&[u8])->u64{let mut chunk=_mm_lddqu_si128(buf.as_ptr()as _);chunk=_mm_madd_epi16(_mm_maddubs_epi16(_mm_sub_epi8(chunk,ZEROS),TEN),HUN);chunk=_mm_madd_epi16(_mm_packus_epi32(chunk,chunk),THO);let res=_mm_cvtsi128_si64(chunk)as u64;((res&0xffffffff)*100_000_000)+(res>>32)}}#[cfg(target_arch="x86_64")]pub(crate)use x86_64::parse16c;}pub use input::{get_stdin_source,FromBytes,Source};pub use output::{get_buffer,Display};#[macro_export]macro_rules!__cargo_equip_macro_def_cpio_scan{(@src$src:ident,@mut[$($mut:tt)?],@id[$v:ident],@ty[$($ty:tt)*],@rest$(,$($rest:tt)*)?)=>{$crate::__cargo_equip::crates::cpio::read_value!(@src$src,@mut[$($mut)?],@id[$v],@ty[$($ty)*]);$crate::__cargo_equip::crates::cpio::scan!(@src$src,$($($rest)*)?);};(@src$src:ident,@mut[$($mut:tt)?],@id[$v:ident],@ty[$($ty:tt)*],@rest$t:tt$($rest:tt)*)=>{$crate::__cargo_equip::crates::cpio::scan!(@src$src,@mut[$($mut)?],@id[$v],@ty[$($ty)*$t],@rest$($rest)*);};(@src$src:ident,@mut[$($mut:tt)?],@rest$v:ident:$($t:tt)*)=>{$crate::__cargo_equip::crates::cpio::scan!(@src$src,@mut[$($mut)?],@id[$v],@ty[],@rest$($t)*);};(@src$src:ident,@mut[],@rest mut$($t:tt)*)=>{$crate::__cargo_equip::crates::cpio::scan!(@src$src,@mut[mut],@rest$($t)*);};(@src$src:ident,$($t:tt)+)=>{$crate::__cargo_equip::crates::cpio::scan!(@src$src,@mut[],@rest$($t)+);};(@src$src:ident,)=>{};($($t:tt)+)=>{let mut __cpio_source_lock_object=$crate::__cargo_equip::crates::cpio::get_stdin_source();$crate::__cargo_equip::crates::cpio::scan!(@src __cpio_source_lock_object,$($t)+);};()=>{::std::compile_error!("Failed to parse macro");}}macro_rules!scan{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_cpio_scan!{$($tt)*})}#[macro_export]macro_rules!__cargo_equip_macro_def_cpio_read_value{(@src$src:ident,@mut[$($mut:tt)?],@id[$v:ident],@ty[$($t:tt)*])=>{let$($mut)?$v=$crate::__cargo_equip::crates::cpio::read_value!(@src$src,@ty[$($t)*]);};(@src$src:ident,@ty[[$($t:tt)*]])=>{$crate::__cargo_equip::crates::cpio::read_value!(@arr@src$src,@ty[],@rest$($t)*)};(@arr@src$src:ident,@ty[$($ty:tt)*],@rest;const$($len:tt)*)=>{{const LEN:usize=($($len)*);let mut arr=[$crate::__cargo_equip::crates::cpio::read_value!(@src$src,@ty[$($ty)*]);LEN];for i in 1..LEN{arr[i]=$crate::__cargo_equip::crates::cpio::read_value!(@src$src,@ty[$($ty)*]);}arr}};(@arr@src$src:ident,@ty[$($ty:tt)*],@rest;$($len:tt)*)=>{{let len=($($len)*);(0..len).map(|_|$crate::__cargo_equip::crates::cpio::read_value!(@src$src,@ty[$($ty)*])).collect::<Vec<_>>()}};(@arr@src$src:ident,@ty[$($ty:tt)*],@rest$t:tt$($rest:tt)*)=>{$crate::__cargo_equip::crates::cpio::read_value!(@arr@src$src,@ty[$($ty)*$t],@rest$($rest)*)};(@src$src:ident,@ty[($($t:tt)*)])=>{$crate::__cargo_equip::crates::cpio::read_value!(@tup@src$src,@ty[],@cur[],@rest$($t)*);};(@tup@src$src:ident,@ty[$([$($ty:tt)*])*],@cur[],@rest)=>{($($crate::__cargo_equip::crates::cpio::read_value!(@src$src,@ty[$($ty)*]),)*)};(@tup@src$src:ident,@ty[$([$($ty:tt)*])*],@cur[$($cur:tt)*],@rest)=>{$crate::__cargo_equip::crates::cpio::read_value!(@tup@src$src,@ty[$([$($ty)*])*[$($cur)*]],@cur[],@rest)};(@tup@src$src:ident,@ty[$([$($ty:tt)*])*],@cur[$($cur:tt)*],@rest,$($rest:tt)*)=>{$crate::__cargo_equip::crates::cpio::read_value!(@tup@src$src,@ty[$([$($ty)*])*[$($cur)*]],@cur[],@rest$($rest)*)};(@tup@src$src:ident,@ty[$([$($ty:tt)*])*],@cur[$($cur:tt)*],@rest$t:tt$($rest:tt)*)=>{$crate::__cargo_equip::crates::cpio::read_value!(@tup@src$src,@ty[$([$($ty)*])*],@cur[$($cur)*$t],@rest$($rest)*)};(@src$src:ident,@ty[$t:ty])=>{{<$t as$crate::__cargo_equip::crates::cpio::FromBytes>::from_bytes($src.next_token())}};(@src$src:ident,@ty[])=>{::std::compile_error!("Failed to parse macro");};}macro_rules!read_value{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_cpio_read_value!{$($tt)*})}#[macro_export]macro_rules!__cargo_equip_macro_def_cpio_put{($arg:expr$(,$args:expr)*,@sep=$sep:expr)=>{$crate::__cargo_equip::crates::cpio::Display::fmt(&$arg,$crate::__cargo_equip::crates::cpio::get_buffer(),$sep);$crate::__cargo_equip::crates::cpio::put!(@tail,$($args),*,@sep=$sep);};(@tail,$($args:expr),*,@sep=$sep:expr)=>{$($crate::__cargo_equip::crates::cpio::Display::fmt(&$sep,$crate::__cargo_equip::crates::cpio::get_buffer(),"");$crate::__cargo_equip::crates::cpio::Display::fmt(&$args,$crate::__cargo_equip::crates::cpio::get_buffer(),$sep);)*};($arg:expr)=>{$crate::__cargo_equip::crates::cpio::Display::fmt(&$arg,$crate::__cargo_equip::crates::cpio::get_buffer(),"");};($($args:expr),*)=>{$crate::__cargo_equip::crates::cpio::put!($($args),*,@sep="\n");};()=>{}}macro_rules!put{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_cpio_put!{$($tt)*})}#[macro_export]macro_rules!__cargo_equip_macro_def_cpio_putln{($($args:expr),+,@sep=$sep:expr)=>{$crate::__cargo_equip::crates::cpio::put!($($args),+,@sep=$sep);$crate::__cargo_equip::crates::cpio::putln!();};($($args:expr),+)=>{$crate::__cargo_equip::crates::cpio::put!($($args),+);$crate::__cargo_equip::crates::cpio::putln!();};()=>{$crate::__cargo_equip::crates::cpio::put!("\n");}}macro_rules!putln{($($tt:tt)*)=>(crate::__cargo_equip_macro_def_cpio_putln!{$($tt)*})}}
        pub mod math {use crate::__cargo_equip::preludes::math::*;mod montgomery{use crate::__cargo_equip::preludes::math::*;#[derive(Debug,Clone,Copy)]pub struct Montgomery<T>{pub(in crate::__cargo_equip::crates::math)modulo:T,pub(in crate::__cargo_equip::crates::math)modulo_inv:T,pub(in crate::__cargo_equip::crates::math)r:T,pub(in crate::__cargo_equip::crates::math)r2:T,}macro_rules!impl_primitive_montgomery{($t:ty,$expand:ty)=>{impl Montgomery<$t>{#[doc=" Convert Montgomery representation to a normal integer representation."]pub const fn reduce(&self,val:$t)->$t{let(t,f)=(((val.wrapping_mul(self.modulo_inv)as$expand).wrapping_mul(self.modulo as$expand)>><$t>::BITS)as$t).overflowing_neg();t.wrapping_add(self.modulo*f as$t)}#[doc=" Multiply `lhs` and `rhs`."]#[doc=" `lhs` and `rhs` must be Montgomery representations."]pub const fn multiply(&self,lhs:$t,rhs:$t)->$t{let a=lhs as$expand*rhs as$expand;let(t,f)=((a>><$t>::BITS)as$t).overflowing_sub((((a as$t).wrapping_mul(self.modulo_inv)as$expand).wrapping_mul(self.modulo as$expand)>><$t>::BITS)as$t,);t.wrapping_add(self.modulo*f as$t)}pub const fn add(&self,lhs:$t,rhs:$t)->$t{let(res,f)=lhs.overflowing_add(rhs);res.wrapping_sub(self.modulo&((f||res>=self.modulo)as$t).wrapping_neg())}pub const fn sub(&self,lhs:$t,rhs:$t)->$t{let(res,f)=lhs.overflowing_sub(rhs);res.wrapping_add(self.modulo&(f as$t).wrapping_neg())}#[doc=" Convert a normal integer representation to Montgomery representation."]#[doc=""]#[doc=" To restore, you can use `Montgomery::reduce`."]#[doc=""]#[doc=" # Examples"]#[doc=" ```rust"]#[doc=" use math::Montgomery;"]#[doc=""]#[doc=" const M: Montgomery<u8> = Montgomery::<u8>::new(17);"]#[doc=" assert_eq!(M.reduce(M.convert(3)), 3);"]#[doc=" ```"]pub const fn convert(&self,val:$t)->$t{self.multiply(val,self.r2)}#[doc=" Calculate `val^exp (mod modulo)`."]#[doc=""]#[doc=" `val` must be Montgomery representation, but `exp` must be a normal integer representation."]pub const fn pow(&self,val:$t,mut exp:u64)->$t{let(mut res,mut val)=(self.r,val);while exp>0{if exp&1!=0{res=self.multiply(res,val);}val=self.multiply(val,val);exp>>=1;}res}#[doc=" Constructor."]#[doc=""]#[doc=" # Panics"]#[doc=" - `modulo` must be odd."]pub const fn new(modulo:$t)->Self{assert!(modulo&1!=0);let r=(((1 as$expand)<<<$t>::BITS)%modulo as$expand)as$t;let r2=((modulo as$expand).wrapping_neg()%modulo as$expand)as$t;let modulo_inv={let mut inv=modulo;while modulo.wrapping_mul(inv)!=1{inv=inv.wrapping_mul((2 as$t).wrapping_sub(modulo.wrapping_mul(inv)));}inv};Self{modulo,modulo_inv,r,r2}}#[doc=" Return `0` in Montgomery representation."]pub const fn zero(&self)->$t{0}#[doc=" Return `1` in Montgomery representation."]pub const fn one(&self)->$t{self.r}#[doc=" Return the modulus."]pub const fn modulus(&self)->$t{self.modulo}}};}impl_primitive_montgomery!(u8,u16);impl_primitive_montgomery!(u16,u32);impl_primitive_montgomery!(u32,u64);impl_primitive_montgomery!(u64,u128);impl_primitive_montgomery!(usize,u128);}use std::collections::HashMap;use arbitrary_montgomery_modint::ArbitraryMontgomeryModint;pub use montgomery::Montgomery;use numeric::Integer;use simple_rand::xor_shift;pub struct ExtendedGcd<T>{pub gcd:T,pub coef:[T;2],pub neg:[bool;2],}pub struct Factors<T:MathInt>{current:T,}pub trait MathInt:Sized+Copy{fn gcd(self,other:Self)->Self;fn lcm(self,other:Self)->Self;fn extended_gcd(self,other:Self)->ExtendedGcd<Self>;fn inverse_mod(self,modulus:Self)->Option<Self>;fn pow_mod(self,exp:u64,modulus:Self)->Self;fn log_mod(self,base:Self,modulus:Self)->Option<Self>;fn sqrt_mod(self,modulus:Self)->Option<Self>;fn crt(self,modulus:Self,other:Self,other_modulus:Self)->Option<(Self,Self)>;fn isqrt(self)->Self;fn is_prime(self)->bool;fn one_of_the_prime_factors(self)->Option<Self>;fn factorize(self)->Factors<Self>;fn divisors(self)->Vec<Self>;fn primitive_root(self)->Self;}macro_rules!impl_math_int_unsigned{($t:ty,$expand:ty,$($witness:expr),*)=>{impl Iterator for Factors<$t>{type Item=($t,u32);fn next(&mut self)->Option<Self::Item>{(self.current>0).then(||{if self.current&1==0{let tr=self.current.trailing_zeros();self.current>>=tr;return Some((2,tr));}self.current.one_of_the_prime_factors().map(|fac|{let mut cnt=0;while self.current%fac==0{self.current/=fac;cnt+=1;}(fac,cnt)})})?}}impl MathInt for$t{#[doc=" Return the greatest common divisor of `self` and `other`."]#[doc=" `gcd(0, 0)` is assumed to be `0`."]#[doc=""]#[doc=" The return value is always non-negative."]#[doc=" Therefore, this method panics if two signed integer minimums (e.g., `i32::MIN`) are passed as arguments"]#[doc=" because it may not return the correct result."]#[doc=""]#[doc=" # Panics"]#[doc=" - One of the arguments must always be greater than the minimum value. (for only signed integer)"]fn gcd(mut self,mut other:Self)->Self{while other!=0{(self,other)=(other,self%other);}self}#[doc=" Return the least common multiple of `self` and `other`."]#[doc=""]#[doc=" # Panics"]#[doc=" - Because this method can overflow in multiplication, panic may occur (in debug mode)"]fn lcm(self,other:Self)->Self{if self==0||other==0{return 0;}self/self.gcd(other)*other}#[doc=" Return `gcd(a, b)`, `a`, `b` satisfying `self * a + other * b = gcd(a, b)`."]#[doc=""]#[doc=" Since the solution can be negative, for unsigned integers, the solution is expressed as a combination of the absolute value of the solution and the sign."]#[doc=""]#[doc=" For signed integers, the returned sign has no meaning and is always `true`."]#[doc=""]#[doc=" # Examples"]#[doc=" ```rust"]#[doc=" use math::{MathInt, ExtendedGcd};"]#[doc=""]#[doc=" // Solve the equation 7x + 11y = 1."]#[doc=" let ExtendedGcd { gcd, mut coef, neg } = 7u32.extended_gcd(11);"]#[doc=" // gcd(7, 11) == 1"]#[doc=" assert_eq!(gcd, 1);"]#[doc=""]#[doc=" coef[0] *= 7;"]#[doc=" coef[1] *= 11;"]#[doc=" // if neg[i] is `true`, coef[i] is negative."]#[doc=" let x = if neg[0] { coef[0].wrapping_neg() } else { coef[0] };"]#[doc=" let y = if neg[1] { coef[1].wrapping_neg() } else { coef[1] };"]#[doc=" assert_eq!(x.wrapping_add(y), gcd);"]#[doc=" ```"]fn extended_gcd(self,other:Self)->ExtendedGcd<Self>{let(mut s,mut sx,mut sy)=(self,1,0);let(mut t,mut tx,mut ty)=(other,0,1);let mut neg=0;while t!=0{let d=s/t;let u=s-t*d;let(ux,uy)=(sx+tx*d,sy+ty*d);(s,sx,sy,t,tx,ty,neg)=(t,tx,ty,u,ux,uy,neg+1);}ExtendedGcd{gcd:s,coef:[sx,sy],neg:[neg>2&&neg&1==1&&sx!=0,neg>1+(self<other)as i32&&neg&1==0&&sy!=0,],}}#[doc=" Return the multiplicative inverse of `self` with `modulus` as the law."]#[doc=" If such number is not found, return `None`."]#[doc=""]#[doc=" # Examples"]#[doc=" ```rust"]#[doc=" use math::MathInt;"]#[doc=""]#[doc=" assert_eq!(3u32.inverse_mod(7), Some(5));"]#[doc=" assert_eq!(5u32.inverse_mod(8), Some(5));"]#[doc=" assert_eq!(2u32.inverse_mod(8), None);"]#[doc=" ```"]fn inverse_mod(self,modulus:Self)->Option<Self>{let ExtendedGcd{gcd,coef,neg}=self.extended_gcd(modulus);(gcd==1).then(||if neg[0]{modulus-coef[0]}else{coef[0]})}#[doc=" Returns the `exp` power of `self` using `modulus` as the law."]#[doc=""]#[doc=" # Panics"]#[doc=" - `modulus > 0` must be satisfied."]#[doc=""]#[doc=" # Examples"]#[doc=" ```rust"]#[doc=" use math::MathInt;"]#[doc=""]#[doc=" assert_eq!(2u32.pow_mod(31, 998244353), (1 << 31) % 998244353);"]#[doc=" assert_eq!(3u32.pow_mod(20, 998244353), 3u32.pow(20) % 998244353);"]#[doc=" ```"]fn pow_mod(self,mut exp:u64,modulus:Self)->Self{assert!(modulus>0);if modulus==1{return 0;}let a=self%modulus;if exp==0||a==1{return 1;}if exp==1{return a;}if modulus&1==1{let mont=Montgomery::<Self>::new(modulus);return mont.reduce(mont.pow(mont.convert(a),exp));}let s=modulus.trailing_zeros();let r=a.pow_mod(exp,modulus>>s);assert!(r<modulus>>s);let(mut res,mut val)=(1,a);while exp>0{if exp&1!=0{res=res.wrapping_mul(val);}val=val.wrapping_mul(val);exp>>=1;}res&=(1<<s)-1;if modulus==1<<s{res}else{r.crt(modulus>>s,res,1<<s).map(|r|r.0).expect("Unexpected panic: `crt` may have bugs")}}#[doc=" Return `x` satisfying `base.pow_mod(x, modulus) == self % modulus`."]#[doc=" If such `x` is not found, return `None`."]#[doc=""]#[doc=" # Panics"]#[doc=" - `modulus > 0` must be satisfied."]#[doc=""]#[doc=" # Examples"]#[doc=" ```rust"]#[doc=" use math::MathInt;"]#[doc=""]#[doc=" assert_eq!(1u32.log_mod(2, 5), Some(0));"]#[doc=" assert_eq!(7u32.log_mod(4, 10), None);"]#[doc=" assert_eq!(6u32.log_mod(8, 10), Some(4));"]#[doc=" assert_eq!(2u32.log_mod(5, 11), None);"]#[doc=" assert_eq!(9u32.log_mod(5, 11), Some(4));"]#[doc=" assert_eq!(0u32.log_mod(0, 1), Some(0));"]#[doc=" assert_eq!(2u32.log_mod(0, 4), None);"]#[doc=" assert_eq!(6u32.log_mod(6, 9), Some(1));"]#[doc=" ```"]fn log_mod(self,base:Self,modulus:Self)->Option<Self>{assert!(modulus>0);let(a,b)=(base%modulus,self%modulus);if modulus==1||b==1{return Some(0);}let ExtendedGcd{gcd,coef,neg}=a.extended_gcd(modulus);if gcd!=1{return(b%gcd==0).then(||{let(na,nb,nm)=(a/gcd,b/gcd,modulus/gcd);let inv_na=na.inverse_mod(nm).expect("Internal Error: inverse_mod may have bugs");(((nb as$expand*inv_na as$expand)%modulus as$expand)as Self).log_mod(a,nm).map(|res|res+1)})?;}let n=(modulus as f64).sqrt().ceil()as Self;assert!(n.saturating_mul(n)>=modulus);let mut map=HashMap::new();let mut aq=1;for i in 0..n{map.entry(aq).or_insert(i);aq=((aq as$expand*a as$expand)%modulus as$expand)as Self;}let inv_a=(if neg[0]{modulus-coef[0]}else{coef[0]}).pow_mod(n as u64,modulus);let mut ap=b;for p in 0..=n{if let Some(q)=map.get(&ap){return Some(p*n+q);}ap=((ap as$expand*inv_a as$expand)%modulus as$expand)as Self;}None}#[doc=" Return `x` satisfying `x.pow_mod(2, modulus) == self % modulus`."]#[doc=" If not found, return `None`."]#[doc=""]#[doc=" Tonelli-Shanks algorithm requires that the law is prime,"]#[doc=" so `modulus` will not accept non-prime numbers."]#[doc=""]#[doc=" # Panics"]#[doc=" - `modulus.is_prime() == true` must be satisfied."]#[doc=""]#[doc=" # Examples"]#[doc=" ```rust"]#[doc=" use math::MathInt;"]#[doc=""]#[doc=" assert_eq!(0u32.sqrt_mod(5).map(|sq| sq * sq % 5), Some(0));"]#[doc=" assert_eq!(1u32.sqrt_mod(5).map(|sq| sq * sq % 5), Some(1));"]#[doc=" assert_eq!(2u32.sqrt_mod(5), None);"]#[doc=" assert_eq!(3u32.sqrt_mod(5), None);"]#[doc=" assert_eq!(4u32.sqrt_mod(5).map(|sq| sq * sq % 5), Some(4));"]#[doc=" assert_eq!(119811886u32.sqrt_mod(197136769).map(|sq| sq as u64 * sq as u64 % 197136769), Some(119811886));"]#[doc=" ```"]fn sqrt_mod(self,modulus:Self)->Option<Self>{assert!(modulus.is_prime());if modulus==2{let res=self&1;return Some(res);}let mont=Montgomery::<Self>::new(modulus);let mn=mont.convert(self);if mn==0{return Some(0);}if modulus&0b11==3{let s=mont.reduce(mont.pow(mn,(modulus as u64+1)>>2));let t=modulus-s;return Some(s.min(t));}if mont.pow(mn,(modulus as u64-1)>>1)!=mont.one(){return None;}let mut rng=xor_shift(381928476372819).map(|b|mont.convert(b as Self%(modulus-2)+2));loop{let b=rng.next()?;if mont.pow(b,(modulus as u64-1)>>1)!=mont.one(){let q=(modulus-1).trailing_zeros()as u64;let s=(modulus as u64-1)>>q;let mut x=mont.pow(mn,(s+1)>>1);let mut x2=mont.multiply(x,x);let mut b=mont.pow(b,s);let mninv=mont.pow(mn,modulus as u64-2);let mut shift=2;while x2!=mn{let diff=mont.multiply(mninv,x2);if mont.pow(diff,1<<(q-shift))!=mont.one(){x=mont.multiply(x,b);b=mont.multiply(b,b);x2=mont.multiply(x2,b);}else{b=mont.multiply(b,b);}shift+=1;}break Some(mont.reduce(x));}}}#[doc=" If x satisfies x = p (mod m) and x = q (mod n) is found, return Some((x, lcm(m,n)))."]#[doc=" Otherwise, return None."]#[doc=" ```ignore"]#[doc=" p + ma = x"]#[doc=" q + nb = x"]#[doc="     => p + ma = q + nb"]#[doc="     => ma - nb = q - p"]#[doc="     => ma = q - p (mod n)"]#[doc=" ```"]#[doc=""]#[doc=" # Panics"]#[doc=" - Both `p < m` and `q < n` must be satisfied."]#[doc=" - `lcm(modulus, other_moduls) <= Self::MAX` must be satisfied."]#[doc=""]#[doc=" # Examples"]#[doc=" ```rust"]#[doc=" use math::MathInt;"]#[doc=""]#[doc=" assert_eq!(2u32.crt(3, 3, 5), Some((8, 15)));"]#[doc=" assert_eq!(3u32.crt(5, 2, 7), Some((23, 35)));"]#[doc=" assert_eq!(2u32.crt(7, 2, 3), Some((2, 21)));"]#[doc=" assert_eq!(2u32.crt(3, 23, 35), Some((23, 105)));"]#[doc=" ```"]fn crt(self,modulus:Self,other:Self,other_modulus:Self)->Option<(Self,Self)>{assert!(self<modulus&&other<other_modulus);if other<self{return other.crt(other_modulus,self,modulus);}if self==other{return Some((self,modulus.lcm(other_modulus)));}let w=other-self;let ExtendedGcd{gcd,coef,neg}=modulus.extended_gcd(other_modulus);(w%gcd==0).then(||{let inv=if neg[0]{other_modulus-coef[0]}else{coef[0]};let k:Self=(inv as$expand*(w/gcd)as$expand%(other_modulus/gcd)as$expand).try_into().expect("lcm(modulus, other_modulus) is too large.");let res=self+modulus*k;debug_assert_eq!(res%modulus,self);debug_assert_eq!(res%other_modulus,other);(res,modulus/gcd*other_modulus)})}#[doc=" Reference : https://doc.rust-lang.org/src/core/num/uint_macros.rs.html"]#[doc=" This is Rust unstable feature, so define here. When isqrt is stabilized, remove this method."]fn isqrt(self)->Self{if self<2{return self;}let mut op=self;let mut res=0;let mut one=1<<(self.ilog2()&!1);while one!=0{if op>=res+one{op-=res+one;res=(res>>1)+one;}else{res>>=1;}one>>=2;}res}#[doc=" Check if `self` is a prime number."]#[doc=""]#[doc=" # Examples"]#[doc=" ```rust"]#[doc=" use math::MathInt;"]#[doc=""]#[doc=" assert!(2u32.is_prime());"]#[doc=" assert!(5u32.is_prime());"]#[doc=" assert!(998244353u32.is_prime());"]#[doc=" assert!(!4u32.is_prime());"]#[doc=" assert!(!561u32.is_prime());"]#[doc=" ```"]fn is_prime(self)->bool{if self==1||self&1==0{return self==2;}let s=(self-1).trailing_zeros();let t=(self-1)>>s;let mont=Montgomery::<Self>::new(self);[$($witness),*].iter().map(|&a|mont.convert(a)).filter(|&a|a!=0).all(|a|{let at=mont.pow(a,t as u64);if at==mont.one()||at==self-mont.one(){return true;}(1..s).scan(at,|at,_|{*at=mont.multiply(*at,*at);Some(*at)}).any(|at|at==self-mont.one())})}#[doc=" Find one of the prime factors of `self`."]#[doc=" If not found, return `None`."]#[doc=""]#[doc=" This method uses Pollard's Rho algorithm."]fn one_of_the_prime_factors(self)->Option<Self>{if self<=1{return None;}if self&1==0{return Some(2);}if self.is_prime(){return Some(self);}let m=(self as f64).powf(0.125).round()as Self+1;let mont=Montgomery::<Self>::new(self);let mut g=1;for c in(1..self).map(|c|mont.convert(c)){let mut y=0;let mut q=mont.one();'base:for r in(0..).map(|i|1<<i){let x=y;(r..=(3*r)>>2).for_each(|_|y=mont.add(mont.multiply(y,y),c));for k in(((3*r)>>2)..r).step_by(m as usize){let ys=y;(0..m.min(r-k)).for_each(|_|{y=mont.add(mont.multiply(y,y),c);q=mont.multiply(q,mont.sub(x,y));});g=mont.reduce(q).gcd(self);if g!=1{if g==self{y=mont.add(mont.multiply(ys,ys),c);while mont.reduce(mont.sub(x,y)).gcd(self)==1{y=mont.add(mont.multiply(y,y),c);}g=mont.reduce(mont.sub(x,y)).gcd(self);}break 'base;}}}if g!=self{break;}}g.one_of_the_prime_factors()}#[doc=" Return an iterator that enumerates prime factors and their number."]#[doc=""]#[doc=" The order of prime factors returned by the iterator is *not defined*."]#[doc=" `1` is not listed."]#[doc=""]#[doc=" # Examples"]#[doc=" ```rust"]#[doc=" use math::MathInt;"]#[doc=""]#[doc=" let mut factors = 108108u32.factorize().collect::<Vec<_>>();"]#[doc=""]#[doc=" // Sorting is required to enumerate prime factors in ascending order."]#[doc=" factors.sort();"]#[doc=" assert_eq!(factors, vec![(2, 2), (3, 3), (7, 1), (11, 1), (13, 1)]);"]#[doc=""]#[doc=" assert_eq!(factors.iter().map(|&(f, c)| f.pow(c)).product::<u32>(), 108108);"]#[doc=" ```"]fn factorize(self)->Factors<Self>{Factors{current:self}}#[doc=" Return the list of the divisors of `self`."]#[doc=" The order of divisors is *not defined*."]#[doc=""]#[doc=" `1` is included in list."]#[doc=""]#[doc=" # Examples"]#[doc=" ```rust"]#[doc=" use math::MathInt;"]#[doc=""]#[doc=" let mut divisors = 108u32.divisors();"]#[doc=""]#[doc=" // Sorting is required to enumerate divisors in ascending order."]#[doc=" divisors.sort();"]#[doc=" assert_eq!(divisors, vec![1, 2, 3, 4, 6, 9, 12, 18, 27, 36, 54, 108])"]#[doc=" ```"]fn divisors(self)->Vec<Self>{let mut f=self.factorize().collect::<Vec<_>>();f.sort();let mut res=vec![1];for(c,cnt)in f{let mut now=1;let len=res.len();for _ in 0..cnt{now*=c;for i in 0..len{let new=res[i]*now;res.push(new);}}}res}#[doc=" Find one of the primitive roots of `self`."]#[doc=""]#[doc=" # Panics"]#[doc=" - `self.is_prime() == true` must be satisfied."]#[doc=""]#[doc=" # Examples"]#[doc=" ```rust"]#[doc=" use math::MathInt;"]#[doc=""]#[doc=" assert_eq!(2u32.primitive_root(), 1);"]#[doc=" assert_eq!(3u32.primitive_root(), 2);"]#[doc=" assert_eq!(5u32.primitive_root(), 2);"]#[doc=" assert_eq!(7u32.primitive_root(), 3);"]#[doc=" assert_eq!(11u32.primitive_root(), 2);"]#[doc=" assert_eq!(13u32.primitive_root(), 2);"]#[doc=" assert_eq!(17u32.primitive_root(), 3);"]#[doc=" assert_eq!(19u32.primitive_root(), 2);"]#[doc=" ```"]fn primitive_root(self)->Self{if self==2{return 1;}assert!(self.is_prime());let factor=(self-1).factorize().map(|v|(self-1)/v.0).collect::<Vec<_>>();let mont=Montgomery::<Self>::new(self);(1..).map(|g|mont.convert(g)).find_map(|g|{factor.iter().all(|&f|mont.pow(g,f as u64)!=mont.one()).then_some(mont.reduce(g)%self)}).unwrap()}}};}impl_math_int_unsigned!(u8,u16,2,7,61);impl_math_int_unsigned!(u16,u32,2,7,61);impl_math_int_unsigned!(u32,u64,2,7,61);impl_math_int_unsigned!(u64,u128,2,325,9375,28178,450775,9780504,1795265022);impl_math_int_unsigned!(usize,u128,2,325,9375,28178,450775,9780504,1795265022);#[inline]pub fn gcd<T:Integer>(mut x:T,mut y:T)->T{while y!=T::zero(){let(nx,ny)=(y,x%y);x=nx;y=ny;}x}#[inline]pub fn lcm<T:Integer>(x:T,y:T)->T{x/gcd(x,y)*y}#[inline]pub fn ext_gcd<T:Integer>(a:T,b:T)->(T,T,T){let(mut s,mut t)=(a,b);let(mut sx,mut tx)=(T::one(),T::zero());let(mut sy,mut ty)=(T::zero(),T::one());while s%t!=T::zero(){let d=s/t;let u=s%t;let ux=sx-tx*d;let uy=sy-ty*d;s=t;sx=tx;sy=ty;t=u;tx=ux;ty=uy;}(t,tx,ty)}#[inline]pub fn mod_pow(a:i64,mut n:i64,p:i64)->i64{let mut res=1;let mut pow=a;while n!=0{if n&1!=0{res=(res as i128*pow as i128%p as i128)as i64;}pow=(pow as i128*pow as i128%p as i128)as i64;n>>=1;}res}#[inline]pub fn mod_log(a:i64,b:i64,p:i64)->Option<i64>{mod_log_with_lower_bound_constraint(a,b,p,0)}pub fn mod_log_with_lower_bound_constraint(a:i64,b:i64,p:i64,lower:i64)->Option<i64>{let(a,b)=(a.rem_euclid(p),b.rem_euclid(p));if p==1{return Some(lower);}if b==1&&lower<=0{return Some(0);}let(g,inv,_)=ext_gcd(a,p);if g!=1{if b%g!=0{return None;}let(na,nb,np)=(a/g,b/g,p/g);let(_,inv,_)=ext_gcd(na,np);let inv=inv.rem_euclid(np);if let Some(res)=mod_log(a,nb*inv,np){return Some(res+1);}else{return None;}}let m=(p as f64).sqrt().ceil()as i64;assert!(m*m>=p);let mut now=1;let mut map=std::collections::HashMap::new();for j in 0..m{map.entry(now).or_insert(vec![]).push(j);now=(now as i128*a as i128%p as i128)as i64;}let inv=mod_pow(inv.rem_euclid(p),m,p);debug_assert_eq!((now as i128*inv as i128).rem_euclid(p as i128),1);let mut now=1;for i in 0..=m{let r=(b as i128*now as i128%p as i128)as i64;if let Some(v)=map.get(&r){for j in v{if i*m+j<lower{continue;}return Some(i*m+j);}}now=(now as i128*inv as i128%p as i128)as i64;}None}pub fn baby_step_giant_step(a:i64,b:i64,p:i64,f:impl Fn(i64,i64)->i64,f_inv:impl Fn(i64,i64)->i64,)->Option<i64>{let m=(p as f64).sqrt().ceil()as i64;assert!(m*m>=p);let mut map=std::collections::HashMap::new();for j in 0..=m{let now=f(a,j);map.entry(now).or_insert(j);}let mut now=f_inv(b,0);for i in 0..=m{if let Some(j)=map.get(&now){return Some(i*m+j);}now=f_inv(now,m);}None}#[inline]pub fn chinese_remainder_theorem(mut a:i64,mut m1:i64,mut b:i64,mut m2:i64,)->Option<(i64,i64)>{if m1<m2{std::mem::swap(&mut a,&mut b);std::mem::swap(&mut m1,&mut m2);}let(a,b)=(a.rem_euclid(m1),b.rem_euclid(m2));if m1%m2==0{return if a%m2!=b{None}else{Some((a,m1))};}let(d,k,_)=ext_gcd(m1,m2);let u1=m2/d;if a%d!=b%d{return None;}let x=(b-a)/d%u1*k%u1;let m=m1*u1;let res=(a+x*m1).rem_euclid(m);Some((res,m))}#[inline]pub fn garner(a:&[i64],p:&[i64],modulo:i64)->(i64,i64){assert_eq!(a.len(),p.len());let mut prod=vec![1;p.len()+1];let mut res=vec![0;p.len()+1];for(i,(&a,&m))in a.iter().zip(p.iter()).enumerate(){let a=a%m;let(_,inv,_)=ext_gcd(prod[i],m);let t=((a-res[i])*inv).rem_euclid(m);for(i,&p)in p.iter().enumerate().skip(i+1){res[i]=(res[i]+(t*prod[i]))%p;prod[i]=(prod[i]*m)%p;}res[p.len()]=(res[p.len()]+(t*prod[p.len()]))%modulo;prod[p.len()]=(prod[p.len()]*m)%modulo;}(res[p.len()],prod[p.len()])}#[inline]pub fn garner_prechecked(a:&[i64],p:&[i64],modulo:i64)->Option<(i64,i64)>{let mut p=p.to_vec();for i in 0..a.len(){for j in 0..i{let mut g=gcd(p[i],p[j]);if(a[i]-a[j])%g!=0{return None;}p[i]/=g;p[j]/=g;let mut gi=gcd(p[i],g);let mut gj=g/gi;g=gcd(gi,gj);gi*=g;gj/=g;while g!=1{g=gcd(gi,gj);gi*=g;gj/=g;}p[i]*=gi;p[j]*=gj;}}Some(garner(a,&p,modulo))}pub fn miller_rabin_test(p:u64)->bool{if p==1||p&1==0{return p==2;}let s=(p-1).trailing_zeros();let t=(p-1)>>s;let mont_zero=ArbitraryMontgomeryModint::raw(0,p);let mont_one=mont_zero.one();let mont_neg_one=mont_zero-mont_one;[2,325,9375,28178,450775,9780504,1795265022].iter().map(|&a|a%p).filter(|&a|a!=0).all(|a|{let a=ArbitraryMontgomeryModint::from_same_mod_unchecked(a,mont_zero);let at=a.pow(t);if at==mont_one||at==mont_neg_one{return true;}(1..s).scan(at,|at,_|{*at*=*at;Some(*at)}).any(|at|at==mont_neg_one)})}pub fn divisors_enumeration(n:u64)->Vec<u64>{let mut f=factorize(n);f.sort();let mut t=vec![];for f in f{match t.last_mut(){Some((c,cnt))if*c==f=>*cnt+=1,_=>t.push((f,1)),}}let mut res=vec![1];for(c,cnt)in t{let mut now=1;let len=res.len();for _ in 0..cnt{now*=c;for i in 0..len{let new=res[i]*now;res.push(new);}}}res}pub fn factorize(mut n:u64)->Vec<u64>{if n==1{return vec![];}let mut res=vec![2u64;n.trailing_zeros()as usize];n>>=n.trailing_zeros();for b in[3,5,7,11,13,17,19]{while n%b==0{res.push(b);n/=b;}}while let Some(g)=pollard_rho(n){while n%g==0{res.push(g);n/=g;}}if n>1{res.push(n);}res}fn pollard_rho(n:u64)->Option<u64>{if n<=1{return None;}if n&1==0{return Some(2);}if miller_rabin_test(n){return Some(n);}let m=(n as f64).powf(0.125).round()as i64+1;let mont_zero=ArbitraryMontgomeryModint::raw(0,n);let mont_one=mont_zero.one();let mut g=1;for c in(1..n).map(|c|ArbitraryMontgomeryModint::from_same_mod_unchecked(c,mont_zero)){let mut y=mont_zero;let mut q=mont_one;'base:for r in(0..).map(|i|1<<i){let x=y;(r..=(3*r)>>2).for_each(|_|y=y*y+c);for k in(((3*r)>>2)..r).step_by(m as usize){let ys=y;(0..m.min(r-k)).for_each(|_|{y=y*y+c;q*=x-y;});g=gcd(q.val()as i64,n as i64);if g!=1{if g==n as i64{y=ys*ys+c;while gcd((x-y).val()as i64,n as i64)==1{y=y*y+c;}g=gcd((x-y).val()as i64,n as i64);}break 'base;}}}if g!=n as i64{break;}}pollard_rho(g as u64)}pub fn tonelli_shanks_unchecked(n:u64,p:u64)->Option<u64>{if p==2{let res=n&1;assert_eq!(res*res%p,n);return Some(res);}type Modint=ArbitraryMontgomeryModint;let mn=Modint::new(n,p);if mn.rawval()==0{assert_eq!(0%p,n);return Some(0);}let one=mn.one();if mn.pow((p-1)>>1).rawval()!=one.rawval(){return None;}if p&0b11==3{let s=mn.pow((p+1)>>2).val();let t=p-s;return Some(s.min(t));}for b in xor_shift(381928476372819).map(|v|v%(p-2)+2){let b=Modint::from_same_mod(b,mn);if b.pow((p-1)>>1).rawval()!=one.rawval(){let q=(p-1).trailing_zeros()as u64;let s=(p-1)>>q;let mut x=mn.pow((s+1)>>1);let mut x2=x*x;let mut b=b.pow(s);let mninv=mn.inv();let mut shift=2;while x2!=mn{let diff=mninv*x2;if diff.pow(1<<(q-shift)).rawval()!=one.rawval(){x*=b;b*=b;x2*=b;}else{b*=b;}shift+=1;}return Some(x.val());}}unreachable!()}pub fn tonelli_shanks(n:u64,p:u64)->Option<u64>{assert!(miller_rabin_test(p));tonelli_shanks_unchecked(n,p)}pub fn xor_base(a:&[u64])->Vec<u64>{let mut res=vec![];for&(mut a)in a{for&base in&res{a=a.min(a^base);}if a>0{res.push(a);}}res}pub struct Sieve<const MAX:usize=1000010>{count:usize,primes:[usize;MAX],}impl<const MAX:usize>Sieve<MAX>{pub const fn new()->Self{let mut primes=[usize::MAX;MAX];let mut count=0;let mut i=2;while i<MAX{if primes[i]==usize::MAX{primes[i]=i;primes[count]=i;count+=1;}let mut j=0;while j<count{if primes[j]>primes[i]||primes[j]*i>=MAX{break;}primes[primes[j]*i]=primes[j];j+=1;}i+=1;}Self{count,primes}}pub const fn count(&self)->usize{self.count}}impl std::ops::Index<usize>for Sieve{type Output=usize;fn index(&self,index:usize)->&Self::Output{&self.primes[index]}}pub fn primitive_root(p:u64)->u64{if p==2{return 1;}assert!(miller_rabin_test(p));let mut factor=factorize(p-1);factor.sort_unstable();factor.dedup();for g in 1..{let mg=ArbitraryMontgomeryModint::new(g,p);if factor.iter().all(|&f|mg.pow((p-1)/f)!=mg.one()){return g%p;}}unreachable!()}}
        pub mod numeric {use crate::__cargo_equip::preludes::numeric::*;pub mod float{use crate::__cargo_equip::preludes::numeric::*;use super::Numeric;use std::ops::Neg;macro_rules!impl_numeric_trait_for_float{($($t:tt)*)=>{$(impl Numeric for$t{fn max_value()->Self{std::$t::MAX}fn min_value()->Self{std::$t::MIN}})*};}impl_numeric_trait_for_float!(f32 f64);pub trait Float:Numeric+Neg<Output=Self>{fn abs(self)->Self;fn acos(self)->Self;fn asin(self)->Self;fn atan(self)->Self;fn atan2(self,other:Self)->Self;fn cbrt(self)->Self;fn ceil(self)->Self;fn cos(self)->Self;fn floor(self)->Self;fn hypot(self,other:Self)->Self;fn is_infinite(self)->bool;fn is_nan(self)->bool;fn max(self,other:Self)->Self;fn min(self,other:Self)->Self;fn mul_add(self,a:Self,b:Self)->Self;fn powf(self,n:Self)->Self;fn powi(self,n:i32)->Self;fn round(self)->Self;fn signum(self)->Self;fn sin(self)->Self;fn sqrt(self)->Self;fn tan(self)->Self;fn to_radians(self)->Self;fn pi()->Self;}macro_rules!impl_float_trait{($($t:tt)*)=>{$(impl Float for$t{fn abs(self)->Self{self.abs()}fn acos(self)->Self{self.acos()}fn asin(self)->Self{self.asin()}fn atan(self)->Self{self.atan()}fn atan2(self,other:Self)->Self{self.atan2(other)}fn cbrt(self)->Self{self.cbrt()}fn ceil(self)->Self{self.ceil()}fn cos(self)->Self{self.cos()}fn floor(self)->Self{self.floor()}fn hypot(self,other:Self)->Self{self.hypot(other)}fn is_infinite(self)->bool{self.is_infinite()}fn is_nan(self)->bool{self.is_nan()}fn max(self,other:Self)->Self{self.max(other)}fn min(self,other:Self)->Self{self.min(other)}fn mul_add(self,a:Self,b:Self)->Self{self.mul_add(a,b)}fn powf(self,n:Self)->Self{self.powf(n)}fn powi(self,n:i32)->Self{self.powi(n)}fn round(self)->Self{self.round()}fn signum(self)->Self{self.signum()}fn sin(self)->Self{self.sin()}fn sqrt(self)->Self{self.sqrt()}fn tan(self)->Self{self.tan()}fn to_radians(self)->Self{self.to_radians()}fn pi()->Self{std::$t::consts::PI}})*};}impl_float_trait!(f32 f64);}pub mod integer{use crate::__cargo_equip::preludes::numeric::*;use super::Numeric;use std::ops::{BitAnd,BitAndAssign,BitOr,BitOrAssign,BitXor,BitXorAssign,Rem,RemAssign,Shl,ShlAssign,Shr,ShrAssign};macro_rules!impl_numeric_trait_for_integer{($($t:tt)*)=>{$(impl Numeric for$t{fn max_value()->Self{std::$t::MAX}fn min_value()->Self{std::$t::MIN}})*};}impl_numeric_trait_for_integer!(i8 i16 i32 i64 i128 isize u8 u16 u32 u64 u128 usize);pub trait Integer:Numeric+Rem<Self,Output=Self>+RemAssign+Shl<i32,Output=Self>+Shl<i64,Output=Self>+Shl<u32,Output=Self>+Shl<u64,Output=Self>+Shl<usize,Output=Self>+Shr<i32,Output=Self>+Shr<i64,Output=Self>+Shr<u32,Output=Self>+Shr<u64,Output=Self>+Shr<usize,Output=Self>+ShlAssign<i32>+ShlAssign<i64>+ShlAssign<u32>+ShlAssign<u64>+ShlAssign<usize>+ShrAssign<i32>+ShrAssign<i64>+ShrAssign<u32>+ShrAssign<u64>+ShrAssign<usize>+BitAnd<Self,Output=Self>+BitOr<Self,Output=Self>+BitXor<Self,Output=Self>+BitAndAssign+BitOrAssign+BitXorAssign+std::hash::Hash+Eq+Ord{fn abs_diff(self,other:Self)->Self;fn count_ones(self)->u32;fn count_zeros(self)->u32;fn div_euclid(self,rhs:Self)->Self;fn leading_ones(self)->u32;fn leading_zeros(self)->u32;fn rem_euclid(self,rhs:Self)->Self;fn reverse_bits(self)->Self;fn rotate_left(self,n:u32)->Self;fn rotate_right(self,n:u32)->Self;fn trailing_ones(self)->u32;fn trailing_zeros(self)->u32;fn overflowing_add(self,rhs:Self)->(Self,bool);fn overflowing_mul(self,rhs:Self)->(Self,bool);fn overflowing_neg(self)->(Self,bool);fn overflowing_sub(self,rhs:Self)->(Self,bool);fn saturating_add(self,rhs:Self)->Self;fn saturating_mul(self,rhs:Self)->Self;fn saturating_sub(self,rhs:Self)->Self;fn wrapping_add(self,rhs:Self)->Self;fn wrapping_mul(self,rhs:Self)->Self;fn wrapping_neg(self)->Self;fn wrapping_sub(self,rhs:Self)->Self;}macro_rules!impl_integer_trait{($($t:ty)*)=>{$(impl Integer for$t{fn abs_diff(self,other:Self)->Self{std::cmp::max(self,other)-std::cmp::min(self,other)}fn count_ones(self)->u32{self.count_ones()}fn count_zeros(self)->u32{self.count_zeros()}fn div_euclid(self,rhs:Self)->Self{self.div_euclid(rhs)}fn leading_ones(self)->u32{(!self).leading_zeros()}fn leading_zeros(self)->u32{self.leading_zeros()}fn rem_euclid(self,rhs:Self)->Self{self.rem_euclid(rhs)}fn reverse_bits(self)->Self{self.reverse_bits()}fn rotate_left(self,n:u32)->Self{self.rotate_left(n)}fn rotate_right(self,n:u32)->Self{self.rotate_right(n)}fn trailing_ones(self)->u32{(!self).trailing_zeros()}fn trailing_zeros(self)->u32{self.trailing_zeros()}fn overflowing_add(self,rhs:Self)->(Self,bool){self.overflowing_add(rhs)}fn overflowing_mul(self,rhs:Self)->(Self,bool){self.overflowing_mul(rhs)}fn overflowing_neg(self)->(Self,bool){self.overflowing_neg()}fn overflowing_sub(self,rhs:Self)->(Self,bool){self.overflowing_sub(rhs)}fn saturating_add(self,rhs:Self)->Self{self.saturating_add(rhs)}fn saturating_mul(self,rhs:Self)->Self{self.saturating_mul(rhs)}fn saturating_sub(self,rhs:Self)->Self{self.saturating_sub(rhs)}fn wrapping_add(self,rhs:Self)->Self{self.wrapping_add(rhs)}fn wrapping_mul(self,rhs:Self)->Self{self.wrapping_mul(rhs)}fn wrapping_neg(self)->Self{self.wrapping_neg()}fn wrapping_sub(self,rhs:Self)->Self{self.wrapping_sub(rhs)}})*};}impl_integer_trait!(i8 i16 i32 i64 i128 isize u8 u16 u32 u64 u128 usize);}pub mod signed{use crate::__cargo_equip::preludes::numeric::*;use std::ops::Neg;pub trait Signed:Neg<Output=Self>+std::marker::Sized{fn is_negative(&self)->bool;fn is_positive(&self)->bool;}macro_rules!impl_integer_trait{($($t:ty)*)=>{$(impl Signed for$t{fn is_negative(&self)->bool{Self::is_negative(*self)}fn is_positive(&self)->bool{Self::is_positive(*self)}})*};}impl_integer_trait!(i8 i16 i32 i64 i128 isize);}pub use float::Float;pub use integer::Integer;pub use signed::Signed;pub use zero_one::{One,Zero};use std::ops::{Add,AddAssign,Div,DivAssign,Mul,MulAssign,Sub,SubAssign};#[derive(Debug)]pub struct Error(pub&'static str);impl std::fmt::Display for Error{fn fmt(&self,f:&mut std::fmt::Formatter<'_>)->std::fmt::Result{write!(f,"{}",self.0)}}impl std::error::Error for Error{}pub trait UnorderedNumeric:Add<Self,Output=Self>+Sub<Self,Output=Self>+Mul<Self,Output=Self>+Div<Self,Output=Self>+AddAssign+SubAssign+MulAssign+DivAssign+std::fmt::Debug+std::fmt::Display+Clone+Copy+PartialEq+Default+Zero+One{}pub trait Numeric:Add<Self,Output=Self>+Sub<Self,Output=Self>+Mul<Self,Output=Self>+Div<Self,Output=Self>+AddAssign+SubAssign+MulAssign+DivAssign+std::fmt::Debug+std::fmt::Display+Clone+Copy+PartialEq+PartialOrd+Default+Zero+One{fn max_value()->Self;fn min_value()->Self;}pub trait IntoFloat:Numeric{fn as_f64(self)->f64;fn as_f32(self)->f32;}impl IntoFloat for i64{fn as_f64(self)->f64{self as f64}fn as_f32(self)->f32{self as f32}}}
        pub mod simple_rand {use std::collections::hash_map::RandomState;use std::hash::{BuildHasher,Hasher};pub fn gen_seed()->u64{let hasher=RandomState::new().build_hasher();hasher.finish()}pub fn xor_shift32(seed:u64)->impl Iterator<Item=u32>{let mut random=seed as u32;std::iter::repeat_with(move||{random^=random<<13;random^=random>>17;random^=random<<5;random})}pub fn xor_shift(seed:u64)->impl Iterator<Item=u64>{let mut random=seed;std::iter::repeat_with(move||{random^=random<<13;random^=random>>7;random^=random<<17;random})}pub fn xor_shift128(seed:u64)->impl Iterator<Item=u128>{let mut x64=xor_shift(seed);std::iter::repeat_with(move||(x64.next().unwrap()as u128)<<64|x64.next().unwrap()as u128)}}
        pub mod __zero_one_0_1_0 {mod one{pub trait One{fn one()->Self;}macro_rules!impl_one_integer{($($t:ty)*)=>{$(impl One for$t{fn one()->$t{1}})*};}impl_one_integer!(i8 i16 i32 i64 i128 isize u8 u16 u32 u64 u128 usize);macro_rules!impl_one_float{($($t:ty)*)=>{$(impl One for$t{fn one()->$t{1.0}})*};}impl_one_float!(f32 f64);}mod zero{pub trait Zero{fn zero()->Self;}macro_rules!impl_zero_integer{($($t:ty)*)=>{$(impl Zero for$t{fn zero()->$t{0}})*};}impl_zero_integer!(i8 i16 i32 i64 i128 isize u8 u16 u32 u64 u128 usize);macro_rules!impl_zero_float{($($t:ty)*)=>{$(impl Zero for$t{fn zero()->$t{0.0}})*};}impl_zero_float!(f32 f64);}pub use one::*;pub use zero::*;}
    }

    pub(crate) mod macros {
        pub mod arbitrary_montgomery_modint {}
        pub mod cpio {pub use crate::{__cargo_equip_macro_def_cpio_put as put,__cargo_equip_macro_def_cpio_putln as putln,__cargo_equip_macro_def_cpio_read_value as read_value,__cargo_equip_macro_def_cpio_scan as scan};}
        pub mod math {}
        pub mod numeric {}
        pub mod simple_rand {}
        pub mod __zero_one_0_1_0 {}
    }

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

    mod preludes {
        pub mod arbitrary_montgomery_modint {}
        pub mod cpio {}
        pub mod math {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::{arbitrary_montgomery_modint,numeric,simple_rand};}
        pub mod numeric {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::__zero_one_0_1_0 as zero_one;}
        pub mod simple_rand {}
        pub mod __zero_one_0_1_0 {}
    }
}