#984167 (Rust) No.187 中華風 (Hard)

提出ソース

結果

問題	No.187 中華風 (Hard)
ユーザー	tayu
提出日時	2024-05-30 21:54:07
言語	Rust (1.77.0)
結果	AC
実行時間	135 ms / 3,000 ms
コード長	34,174 bytes
コンパイル時間	15,373 ms
コンパイル使用メモリ	404,488 KB
実行使用メモリ	6,944 KB
最終ジャッジ日時	2024-05-30 21:54:27
合計ジャッジ時間	18,160 ms
ジャッジサーバーID （参考情報）	judge4 / judge5

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	1 ms 6,816 KB
testcase_01	AC	1 ms 6,812 KB
testcase_02	AC	100 ms 6,944 KB
testcase_03	AC	98 ms 6,944 KB
testcase_04	AC	135 ms 6,940 KB
testcase_05	AC	133 ms 6,940 KB
testcase_06	AC	132 ms 6,944 KB
testcase_07	AC	132 ms 6,940 KB
testcase_08	AC	92 ms 6,944 KB
testcase_09	AC	93 ms 6,940 KB
testcase_10	AC	92 ms 6,940 KB
testcase_11	AC	135 ms 6,940 KB
testcase_12	AC	133 ms 6,944 KB
testcase_13	AC	23 ms 6,940 KB
testcase_14	AC	23 ms 6,944 KB
testcase_15	AC	94 ms 6,940 KB
testcase_16	AC	96 ms 6,944 KB
testcase_17	AC	1 ms 6,940 KB
testcase_18	AC	1 ms 6,940 KB
testcase_19	AC	1 ms 6,940 KB
testcase_20	AC	101 ms 6,944 KB
testcase_21	AC	1 ms 6,940 KB
testcase_22	AC	132 ms 6,940 KB
testcase_23	AC	1 ms 6,944 KB
testcase_24	AC	1 ms 6,940 KB

権限があれば一括ダウンロードができます

コンパイルメッセージ

warning: trailing semicolon in macro used in expression position
  --> src/main.rs:38:13242
   |
10 |     scan!(n: usize, p: [(i64, i64); n]);
   |     ----------------------------------- in this macro invocation
...
38 |         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=1

ソースコード

raw source code

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

use cpio::*;
use math::garner_prechecked;

const MOD: i64 = 1_000_000_007;

fn main() {
    scan!(n: usize, p: [(i64, i64); n]);

    let (a, p) = p.into_iter().unzip::<i64, i64, Vec<_>, Vec<_>>();

    let f = a.iter().all(|a| *a == 0);

    if let Some((res, lcm)) = garner_prechecked(&a, &p, MOD) {
        if f {
            putln!(lcm);
        } else {
            putln!(res);
        }
    } else {
        putln!("-1");
    }
}

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

///  # Bundled libraries
/// 
///  - `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`
///  - `simple-rand 0.1.0 (path+███████████████████████████████████████████)`                                  published in **missing** licensed under `CC0-1.0` as `crate::__cargo_equip::crates::simple_rand`
#[cfg_attr(any(), rustfmt::skip)]
#[allow(unused)]
mod __cargo_equip {
    pub(crate) mod crates {
        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;pub use montgomery::Montgomery;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,}macro_rules!impl_factors{($($t:ty),*)=>{$(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_factors!(u8,u16,u32,u64,usize,i8,i16,i32,i64,isize);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 sqrti(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!overflow_err{($method:literal)=>{::std::concat!("Overflow occurs in ",$method," for signed integer")};}macro_rules!impl_math_int_unsigned{($t:ty,$st:ty,$expand:ty,$($witness:expr),*)=>{impl MathInt for$t{fn gcd(mut self,mut other:Self)->Self{while other!=0{(self,other)=(other,self%other);}self}fn lcm(self,other:Self)->Self{if self==0||other==0{return 0;}self/self.gcd(other)*other}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,],}}fn inverse_mod(self,modulus:Self)->Option<Self>{assert!(modulus>0);let ExtendedGcd{gcd,coef,neg}=self.extended_gcd(modulus);(gcd==1).then(||if neg[0]{modulus-coef[0]}else{coef[0]})}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 as$t,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")}}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}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));}}}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)})}fn sqrti(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}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())})}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()}fn factorize(self)->Factors<Self>{Factors{current:self}}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}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 MathInt for$st{fn gcd(self,other:Self)->Self{self.unsigned_abs().gcd(other.unsigned_abs()).try_into().expect(overflow_err!("MathInt::gcd"))}fn lcm(self,other:Self)->Self{self.unsigned_abs().lcm(other.unsigned_abs()).try_into().expect(overflow_err!("MathInt::lcm"))}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);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)=(t,tx,ty,u,ux,uy);}if s<0{const ERR:&str=overflow_err!("MathInt::extended_gcd");s=s.checked_neg().expect(ERR);sx=s.checked_neg().expect(ERR);sy=s.checked_neg().expect(ERR);}ExtendedGcd{gcd:s,coef:[sx,sy],neg:[true;2]}}fn inverse_mod(self,modulus:Self)->Option<Self>{assert!(modulus>0);(self.rem_euclid(modulus)as$t).inverse_mod(modulus as$t).map(|inv|inv as Self)}fn pow_mod(self,exp:u64,modulus:Self)->Self{assert!(modulus>0);(self.rem_euclid(modulus)as$t).pow_mod(exp,modulus as$t)as Self}fn log_mod(self,base:Self,modulus:Self)->Option<Self>{assert!(modulus>0);(self.rem_euclid(modulus)as$t).log_mod(base.rem_euclid(modulus)as$t,modulus as$t).map(|log|log as Self)}fn sqrt_mod(self,modulus:Self)->Option<Self>{assert!(modulus>0);(self.rem_euclid(modulus)as$t).sqrt_mod(modulus as$t).map(|sq|sq as Self)}fn crt(self,modulus:Self,other:Self,other_modulus:Self)->Option<(Self,Self)>{assert!(modulus>0&&other_modulus>0);(self.rem_euclid(modulus)as$t).crt(modulus as$t,other.rem_euclid(other_modulus)as$t,other_modulus as$t,).map(|(x,lcm)|{(x.try_into().expect(overflow_err!("MathInt::crt")),lcm.try_into().expect(overflow_err!("MathInt::crt")),)})}fn sqrti(self)->Self{assert!(self>=0);(self as$t).sqrti()as Self}fn is_prime(self)->bool{self>1&&(self as$t).is_prime()}fn one_of_the_prime_factors(self)->Option<Self>{self.is_positive().then(||(self as$t).one_of_the_prime_factors().map(|f|f as Self))?}fn factorize(self)->Factors<Self>{Factors{current:self}}fn divisors(self)->Vec<Self>{if self<=0{return vec![];}(self as$t).divisors().into_iter().map(|d|d as Self).collect()}fn primitive_root(self)->Self{assert!(self>=0);(self as$t).primitive_root()as Self}}};}impl_math_int_unsigned!(u8,i8,u16,2,7,61);impl_math_int_unsigned!(u16,i16,u32,2,7,61);impl_math_int_unsigned!(u32,i32,u64,2,7,61);impl_math_int_unsigned!(u64,i64,u128,2,325,9375,28178,450775,9780504,1795265022);impl_math_int_unsigned!(usize,isize,u128,2,325,9375,28178,450775,9780504,1795265022);#[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 ExtendedGcd{gcd,coef,neg:_}=a.extended_gcd(p);let(g,inv)=(gcd,coef[0].rem_euclid(p));if g!=1{if b%g!=0{return None;}let(na,nb,np)=(a/g,b/g,p/g);let inv=na.inverse_mod(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=inv.rem_euclid(p).pow_mod(m as u64,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 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=prod[i].inverse_mod(m).expect("math::garner : inverse_mod is not found");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=p[i].gcd(p[j]);if(a[i]-a[j])%g!=0{return None;}p[i]/=g;p[j]/=g;let mut gi=p[i].gcd(g);let mut gj=g/gi;g=gi.gcd(gj);gi*=g;gj/=g;while g!=1{g=gi.gcd(gj);gi*=g;gj/=g;}p[i]*=gi;p[j]*=gj;}}Some(garner(a,&p,modulo))}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 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(crate) mod macros {
        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 simple_rand {}
    }

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

    mod preludes {
        pub mod cpio {}
        pub mod math {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::simple_rand;}
        pub mod simple_rand {}
    }
}