結果

問題 No.3398 Accuracy of Integer Division Approximate Function 2
コンテスト
ユーザー 👑 Mizar
提出日時 2025-11-02 15:16:20
言語 Rust
(1.83.0 + proconio)
結果
AC  
実行時間 324 ms / 2,000 ms
コード長 26,934 bytes
記録
コンパイル時間 13,646 ms
コンパイル使用メモリ 400,552 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2025-12-04 23:30:56
合計ジャッジ時間 16,905 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

// main.rs

#![forbid(unsafe_code)]
#![allow(clippy::many_single_char_names)]

use crate::bigint::BigIInt as BI;
use crate::input_lite::*;

fn main() {
    use std::io::Write;
    let mut bw = std::io::BufWriter::new(std::io::stdout());
    input! { t: usize }
    for _ in 0..t {
        input! { d: BI, a: BI, b: BI, k: BI }
        let ans: BI = compute_xmin(&d, &a, &b, &k);
        writeln!(bw, "{}", ans).unwrap();
    }
}

fn compute_xmin(d: &BI, a: &BI, b: &BI, k: &BI) -> BI {
    let gcd_da = d.gcd(a);
    let (d_red, a_red) = (d / &gcd_da, a / &gcd_da);
    let (m_red, r_red) = (&a_red * b).checked_div_rem_trunc(&d_red).unwrap();
    let m_red_neg = -&m_red;
    let t_delta = b * k;
    if r_red.is_zero() && &(&d_red * k) + 1u64 >= a_red {
        return BI::from(-1i64);
    }
    let (mut lo, mut hi) = (BI::zero(), &(&(&a_red * b) * k) + 2u64);
    let zero = BI::zero();
    while (&lo + 1u64) < hi {
        let mid = &(&lo + &hi) >> 1;
        if mwf(&mid, &a_red, &b, &m_red_neg, &d_red, &zero) <= t_delta {
            lo = mid;
        } else {
            hi = mid;
        }
    }
    d * &lo
}

fn mwf(n: &BI, m: &BI, a: &BI, b: &BI, c: &BI, d: &BI) -> BI {
    assert!(n.is_positive() && m.is_positive());
    let (mut sum_acc, mut max_acc, mut n, mut m, mut a, mut b, mut c, mut d) = (
        BI::zero(),
        &d.checked_div_rem_floor(m).unwrap().0 * &b,
        n.clone(),
        m.clone(),
        a.clone(),
        b.clone(),
        c.clone(),
        d.clone(),
    );
    loop {
        let q;
        (q, c) = c.checked_div_rem_floor(&m).unwrap();
        a += &(&b * &q);
        let q;
        (q, d) = d.checked_div_rem_floor(&m).unwrap();
        sum_acc += &(&b * &q);
        max_acc = max_acc.max(sum_acc.clone());
        let n1 = &n - 1u64;
        let y_max = {
            let mut y = &c * &n1;
            y += &d;
            y /= &m;
            y
        };
        if y_max.is_zero() {
            return max_acc.max(&sum_acc + &(&a * &n1));
        }
        if !a.is_negative() {
            max_acc = max_acc.max(&sum_acc + &(&(&a * &n1) + &(&b * &y_max)));
        } else {
            sum_acc += &(&a + &b);
        }
        n = y_max;
        d = &(&m - &d) - 1u64;
        std::mem::swap(&mut a, &mut b);
        std::mem::swap(&mut c, &mut m);
    }
}

#[rustfmt::skip]pub mod bigint{#[derive(Clone,Eq,PartialEq)]pub struct BigUInt{pub data:Vec<u64>,}impl BigUInt{pub fn with_capacity(capacity:usize)->Self{Self{data:Vec::with_capacity(capacity),}}pub fn zero()->Self{Self{data:Vec::new()}}pub fn one()->Self{Self{data:[1u64][..].into(),}}pub fn is_zero(&self)->bool{self.data.is_empty()}pub fn is_positive(&self)->bool{!self.is_zero()}pub fn is_negative(&self)->bool{false}pub fn from_dec_str(s:&str)->Result<Self,&'static str>{let s=s.trim();if s.is_empty(){return Err(ERRMSG_EMPTY_STRING);}if s.bytes().any(|b|!b.is_ascii_digit()){return Err(ERRMSG_INVALID_CHAR);}let mut acc=BigUInt::zero();for ch in s.as_bytes().rchunks(19).rev(){acc.mul_assign_small(DEC_BASE);acc.add_assign_small(str::from_utf8(ch).unwrap().parse::<u64>().unwrap());}Ok(acc)}pub fn to_dec_string(&self)->String{if self.is_zero(){return "0".to_string();}let mut v=self.clone();let mut d:Vec<u64> =Vec::with_capacity(self.data.len()+self.data.len()/64+1);while!v.is_zero(){let r;(v,r)=v.checked_div_rem_small(DEC_BASE).unwrap();d.push(r);}let mut out=String::with_capacity(d.len()*19);out.push_str(&d.pop().unwrap().to_string());for&e in d.iter().rev(){out.push_str(&format!("{:019}",e));}out}pub fn normalize(&mut self){while self.data.last().is_some_and(|&x|x==0){self.data.pop();}}pub fn from_u64(x:u64)->Self{match x{0=>Self::zero(),_=>Self{data:[x][..].into(),},}}pub fn from_u128(x:u128)->Self{let(lo,hi)=(x as u64,(x>>64)as u64);match(lo,hi){(0,0)=>Self::zero(),(_,0)=>Self{data:[lo][..].into(),},_=>Self{data:[lo,hi][..].into(),},}}fn cmp_impl(&self,rhs:&Self)->Ordering{assert!(self.data.last()!=Some(&0)&&rhs.data.last()!=Some(&0));match self.data.len().cmp(&rhs.data.len()){Less=>Less,Greater=>Greater,Equal=>{for(a,b)in self.data.iter().rev().zip(rhs.data.iter().rev()){match a.cmp(b){Less=>return Less,Greater=>return Greater,Equal=>{}}}Equal}}}pub fn cmp_u64(&self,rhs:u64)->Ordering{if self.is_zero(){if rhs==0{return Equal;}else{return Less;}}if self.data.len()==1&&self.data[0]==rhs{return Equal;}if self.data.len()>1||self.data[0]>rhs{return Greater;}Less}pub fn add_assign_small(&mut self,rhs:u64){let mut carry=rhs;for limb in self.data.iter_mut(){let(sum,carry1)=limb.overflowing_add(carry);*limb=sum;if!carry1{return;}carry=carry1 as u64;}self.data.push(carry);}pub fn add_small(&self,rhs:u64)->Self{let mut v=self.clone();v.add_assign_small(rhs);v}pub fn saturating_sub_assign_small(&mut self,rhs:u64)->bool{let mut borrow=rhs;for limb in self.data.iter_mut(){let(diff1,borrow1)=limb.overflowing_sub(borrow);*limb=diff1;borrow=borrow1 as u64;if borrow==0{self.normalize();return false;}}if borrow==0{self.normalize();false}else{self.data.clear();true}}pub fn saturating_sub_small(&self,rhs:u64)->Self{let mut v=self.clone();v.saturating_sub_assign_small(rhs);v}pub fn checked_sub_small(&self,rhs:u64)->Option<Self>{let mut v=self.clone();if v.saturating_sub_assign_small(rhs){return None;}Some(v)}pub fn mul_assign_small(&mut self,rhs:u64){if rhs==0||self.is_zero(){self.data.clear();return;}let mut carry=0u64;for limb in self.data.iter_mut(){let word=(*limb as u128)*(rhs as u128)+(carry as u128);*limb=word as u64;carry=(word>>64)as u64;}if carry!=0{self.data.push(carry);}}pub fn mul_small(&self,rhs:u64)->Self{let mut v=self.clone();v.mul_assign_small(rhs);v}pub fn checked_div_rem_small(&self,rhs:u64)->Option<(Self,u64)>{if rhs==0{return None;}let mut acc=self.clone();let mut rem=0u64;for limb in acc.data.iter_mut().rev(){let dividend=((rem as u128)<<64)|(*limb as u128);(*limb,rem)=((dividend/(rhs as u128))as u64,(dividend%(rhs as u128))as u64,);}acc.normalize();Some((acc,rem))}pub fn add_assign_impl(&mut self,rhs:&Self){if self.data.len()<rhs.data.len(){self.data.resize(rhs.data.len(),0);}let mut carry=false;for(limb,&rhs_limb)in self.data.iter_mut().zip(rhs.data.iter()){let(sum1,carry1)=limb.overflowing_add(rhs_limb);let(sum2,carry2)=sum1.overflowing_add(carry as u64);*limb=sum2;carry=carry1||carry2;}for limb in&mut self.data[rhs.data.len()..]{if!carry{break;}let(sum,carry1)=limb.overflowing_add(1);*limb=sum;carry=carry1;}if carry{self.data.push(1);}}fn add_impl(&self,rhs:&Self)->Self{let min_len=self.data.len().min(rhs.data.len());let mut v=Self::with_capacity(self.data.len().max(rhs.data.len())+1);let mut carry=false;for(a,b)in self.data.iter().zip(rhs.data.iter()){let(sum1,carry1)=a.overflowing_add(*b);let(sum2,carry2)=sum1.overflowing_add(carry as u64);v.data.push(sum2);carry=carry1||carry2;}if self.data.len()>min_len{v.data.extend_from_slice(&self.data[min_len..]);}else{v.data.extend_from_slice(&rhs.data[min_len..]);}for limb in&mut v.data[min_len..]{if!carry{break;}let(sum,carry1)=limb.overflowing_add(1);*limb=sum;carry=carry1;}v}pub fn saturating_sub_assign_impl(&mut self,rhs:&Self)->bool{if self.data.len()<rhs.data.len(){self.data.clear();return true;}let mut borrow=false;for(limb,&rhs_limb)in self.data.iter_mut().zip(rhs.data.iter()){let(diff1,borrow1)=limb.overflowing_sub(rhs_limb);let(diff2,borrow2)=diff1.overflowing_sub(borrow as u64);*limb=diff2;borrow=borrow1||borrow2;}for limb in&mut self.data[rhs.data.len()..]{if!borrow{break;}let(diff,borrow1)=limb.overflowing_sub(1);*limb=diff;borrow=borrow1;}if borrow{self.data.clear();true}else{self.normalize();false}}pub fn saturating_sub_impl(&self,rhs:&Self)->Self{let mut v=self.clone();v.saturating_sub_assign_impl(rhs);v}pub fn checked_sub_impl(&self,rhs:&Self)->Option<Self>{let mut v=self.clone();if v.saturating_sub_assign_impl(rhs){return None;}Some(v)}pub fn shl_assign_impl(&mut self,bits:u32){if self.is_zero(){return;}let shift_limbs=(bits/u64::BITS)as usize;if shift_limbs>0{self.data.splice(0..0,std::iter::repeat(0u64).take(shift_limbs));}let bits=bits%u64::BITS;if bits==0{return;}let mut carry=0u64;for limb in&mut self.data[shift_limbs..]{let new_carry=*limb>>(u64::BITS-bits);*limb=(*limb<<bits)|carry;carry=new_carry;}if carry!=0{self.data.push(carry);}}pub fn shr_assign_impl(&mut self,bits:u32){let shift_limbs=(bits/u64::BITS)as usize;if shift_limbs>=self.data.len(){self.data.clear();return;}self.data.drain(0..shift_limbs);let bits=bits%u64::BITS;if bits==0{return;}for i in shift_limbs..self.data.len(){let low=self.data[i]>>bits;let high=self.data.get(i+1).copied().unwrap_or(0)<<(u64::BITS-bits);self.data[i]=low|high;}self.normalize();}fn shl_impl(&self,bits:u32)->Self{let mut v=self.clone();v.shl_assign_impl(bits);v}fn shr_impl(&self,bits:u32)->Self{let mut v=self.clone();v.shr_assign_impl(bits);v}fn mul_impl(&self,rhs:&Self)->Self{if self.is_zero()||rhs.is_zero(){return BigUInt::zero();}let n=self.data.len();let m=rhs.data.len();let mut out=vec![0u64;n+m];for i in 0..n{let ai=self.data[i]as u128;let mut carry:u64=0;for j in 0..m{let idx=i+j;let t=ai*(rhs.data[j]as u128)+(out[idx]as u128)+(carry as u128);out[idx]=t as u64;carry=(t>>64)as u64;}let mut k=i+m;while carry!=0{let t=(out[k]as u128)+(carry as u128);out[k]=t as u64;carry=(t>>64)as u64;k+=1;}}let mut z=BigUInt{data:out.into()};z.normalize();z}pub fn checked_div_rem(&self,rhs:&Self)->Option<(Self,Self)>{if rhs.is_zero(){return None;}match self.cmp_impl(rhs){Less=>return Some((BigUInt::zero(),self.clone())),Equal=>return Some((BigUInt::one(),BigUInt::zero())),Greater=>{}}if rhs.data.len()==1{let(q,r)=self.checked_div_rem_small(rhs.data[0]).unwrap();return Some((q,Self::from(r)));}let top=*rhs.data.last().unwrap_or(&0);let shift=if top==0{0}else{top.leading_zeros()};let mut u=self.shl(shift);let v=rhs.shl(shift);let n=v.data.len();let m=u.data.len().saturating_sub(n);u.data.push(0);let mut q=vec![0u64;m+1];let v_hi=v.data.get(n-1).copied().unwrap_or(0)as u128;let v_2nd=v.data.get(n-2).copied().unwrap_or(0)as u128;for j in(0..=m).rev(){let u_jn_hi=u.data.get(j+n).copied().unwrap_or(0)as u128;let u_jn_lo=u.data.get(j+n-1).copied().unwrap_or(0)as u128;let u_jn=(u_jn_hi<<u64::BITS)|u_jn_lo;let mut qhat=if v_hi==0{0}else{u_jn/v_hi};let mut rhat=if v_hi==0{0}else{u_jn%v_hi};if qhat>u64::MAX as u128{qhat=u64::MAX as u128;rhat=u_jn-qhat*v_hi;}while qhat*v_2nd>(rhat<<u64::BITS)+(u.data.get(j+n-2).copied().unwrap_or(0)as u128){if qhat==0{break;}qhat-=1;rhat=rhat.saturating_add(v_hi);if rhat>=(1u128<<u64::BITS){break;}}let mut borrow:i128=0;let mut carry_mul:u128=0;for i in 0..n{let vi=v.data.get(i).copied().unwrap_or(0)as u128;let ui=u.data.get(j+i).copied().unwrap_or(0)as i128;let p=qhat*vi+carry_mul;carry_mul=p>>u64::BITS;let p_lo=p as u64;let uu=ui-(p_lo as i128)+borrow;if uu<0{if let Some(slot)=u.data.get_mut(j+i){*slot=(uu+(1i128<<u64::BITS))as u64;}borrow=-1;}else{if let Some(slot)=u.data.get_mut(j+i){*slot=uu as u64;}borrow=0;}}let tail=u.data.get(j+n).copied().unwrap_or(0)as i128;let uu=tail-(carry_mul as i128)+borrow;if uu<0{if qhat>0{qhat-=1;}let mut carry2:u128=0;for i in 0..n{let t=(u.data.get(j+i).copied().unwrap_or(0)as u128)+(v.data.get(i).copied().unwrap_or(0)as u128)+carry2;if let Some(slot)=u.data.get_mut(j+i){*slot=t as u64;}carry2=t>>u64::BITS;}if let Some(slot)=u.data.get_mut(j+n){let t=(*slot as u128)+carry2;*slot=t as u64;}}else{if let Some(slot)=u.data.get_mut(j+n){*slot=uu as u64;}}if let Some(slot)=q.get_mut(j){*slot=qhat as u64;}}let mut r=BigUInt{data:u.data.get(..n).unwrap_or(&[]).into(),};r.shr_assign_impl(shift);let mut qq=BigUInt{data:q.into()};qq.normalize();r.normalize();Some((qq,r))}}impl Default for BigUInt{fn default()->Self{Self{data:Vec::new()}}}impl fmt::Debug for BigUInt{fn fmt(&self,f:&mut fmt::Formatter<'_>)->fmt::Result{write!(f,"0x")?;for(i,limb)in self.data.iter().enumerate().rev(){if i==self.data.len()-1{write!(f,"{limb:X}")?;}else{write!(f,"{limb:016X}")?;}}if self.data.is_empty(){write!(f,"0")?;}Ok(())}}impl fmt::Display for BigUInt{fn fmt(&self,f:&mut fmt::Formatter<'_>)->fmt::Result{if self.is_zero(){return write!(f,"0");}let s=self.to_dec_string();write!(f,"{s}")}}impl str::FromStr for BigUInt{type Err=&'static str;fn from_str(s:&str)->Result<Self,Self::Err>{BigUInt::from_dec_str(s)}}impl From<u64>for BigUInt{fn from(x:u64)->Self{BigUInt::from_u64(x)}}impl From<u128>for BigUInt{fn from(x:u128)->Self{BigUInt::from_u128(x)}}impl Add for&BigUInt{type Output=BigUInt;fn add(self,rhs:&BigUInt)->BigUInt{self.add_impl(rhs)}}impl Add for BigUInt{type Output=BigUInt;fn add(self,rhs:BigUInt)->BigUInt{(&self).add_impl(&rhs)}}impl Sub for&BigUInt{type Output=BigUInt;fn sub(self,rhs:&BigUInt)->BigUInt{self.saturating_sub_impl(rhs)}}impl Mul for&BigUInt{type Output=BigUInt;fn mul(self,rhs:&BigUInt)->BigUInt{self.mul_impl(rhs)}}impl Div for&BigUInt{type Output=BigUInt;fn div(self,rhs:&BigUInt)->BigUInt{self.checked_div_rem(rhs).expect(ERRMSG_DIVIDE_BY_ZERO).0}}impl Rem for&BigUInt{type Output=BigUInt;fn rem(self,rhs:&BigUInt)->BigUInt{self.checked_div_rem(rhs).expect(ERRMSG_DIVIDE_BY_ZERO).1}}impl Shl<u32>for&BigUInt{type Output=BigUInt;fn shl(self,bits:u32)->BigUInt{self.shl_impl(bits)}}impl Shr<u32>for&BigUInt{type Output=BigUInt;fn shr(self,bits:u32)->BigUInt{self.shr_impl(bits)}}impl PartialOrd for BigUInt{fn partial_cmp(&self,rhs:&Self)->Option<Ordering>{Some(self.cmp_impl(rhs))}}impl Ord for BigUInt{fn cmp(&self,rhs:&Self)->Ordering{self.cmp_impl(rhs)}}impl Add<u64>for&BigUInt{type Output=BigUInt;fn add(self,rhs:u64)->BigUInt{self.add_small(rhs)}}impl Sub<u64>for&BigUInt{type Output=BigUInt;fn sub(self,rhs:u64)->BigUInt{self.checked_sub_small(rhs).expect(ERRMSG_UNDERFLOW)}}impl Mul<u64>for&BigUInt{type Output=BigUInt;fn mul(self,rhs:u64)->BigUInt{self.mul_small(rhs)}}impl Div<u64>for&BigUInt{type Output=BigUInt;fn div(self,rhs:u64)->BigUInt{self.checked_div_rem_small(rhs).expect(ERRMSG_DIVIDE_BY_ZERO).0}}impl Rem<u64>for&BigUInt{type Output=BigUInt;fn rem(self,rhs:u64)->BigUInt{self.checked_div_rem_small(rhs).expect(ERRMSG_DIVIDE_BY_ZERO).1.into()}}impl AddAssign<&BigUInt>for BigUInt{fn add_assign(&mut self,rhs:&BigUInt){self.add_assign_impl(rhs);}}impl SubAssign<&BigUInt>for BigUInt{fn sub_assign(&mut self,rhs:&BigUInt){self.saturating_sub_assign_impl(rhs);}}impl AddAssign<u64>for BigUInt{fn add_assign(&mut self,rhs:u64){self.add_assign_small(rhs);}}impl SubAssign<u64>for BigUInt{fn sub_assign(&mut self,rhs:u64){self.saturating_sub_assign_small(rhs);}}impl MulAssign<u64>for BigUInt{fn mul_assign(&mut self,rhs:u64){self.mul_assign_small(rhs);}}impl DivAssign<u64>for BigUInt{fn div_assign(&mut self,rhs:u64){*self=self.checked_div_rem_small(rhs).expect(ERRMSG_DIVIDE_BY_ZERO).0;}}impl RemAssign<u64>for BigUInt{fn rem_assign(&mut self,rhs:u64){*self=self.checked_div_rem_small(rhs).expect(ERRMSG_DIVIDE_BY_ZERO).1.into();}}impl BitAnd for&BigUInt{type Output=BigUInt;fn bitand(self,rhs:&BigUInt)->BigUInt{let min_len=self.data.len().min(rhs.data.len());let mut out=vec![0u64;min_len];for(o,(a,b))in out.iter_mut().zip(self.data.iter().zip(rhs.data.iter())){*o=a&b;}let mut result=BigUInt{data:out};result.normalize();result}}impl BitOr for&BigUInt{type Output=BigUInt;fn bitor(self,rhs:&BigUInt)->BigUInt{let max_len=self.data.len().max(rhs.data.len());let mut out=vec![0u64;max_len];for(o,(a,b))in out.iter_mut().zip(self.data.iter().zip(rhs.data.iter())){*o=a|b;}let mut result=BigUInt{data:out};result.normalize();result}}impl BitXor for&BigUInt{type Output=BigUInt;fn bitxor(self,rhs:&BigUInt)->BigUInt{let max_len=self.data.len().max(rhs.data.len());let mut out=vec![0u64;max_len];for(o,(a,b))in out.iter_mut().zip(self.data.iter().zip(rhs.data.iter())){*o=a^b;}let mut result=BigUInt{data:out};result.normalize();result}}impl BitAndAssign<&BigUInt>for BigUInt{fn bitand_assign(&mut self,rhs:&BigUInt){if self.data.len()>rhs.data.len(){self.data.truncate(rhs.data.len());}for(a,b)in self.data.iter_mut().zip(rhs.data.iter()){*a&=*b;}self.normalize();}}impl BitOrAssign<&BigUInt>for BigUInt{fn bitor_assign(&mut self,rhs:&BigUInt){if self.data.len()<rhs.data.len(){self.data.resize(rhs.data.len(),0);}for(a,b)in self.data.iter_mut().zip(rhs.data.iter()){*a|=*b;}}}impl BitXorAssign<&BigUInt>for BigUInt{fn bitxor_assign(&mut self,rhs:&BigUInt){if self.data.len()<rhs.data.len(){self.data.resize(rhs.data.len(),0);}for(a,b)in self.data.iter_mut().zip(rhs.data.iter()){*a^=*b;}self.normalize();}}#[derive(Clone,Copy,Debug,Eq,PartialEq)]pub enum Sign{Negative=-1,Zero=0,Positive=1,}impl Mul for&Sign{type Output=Sign;fn mul(self,rhs:&Sign)->Sign{match(self,rhs){(Zero,_)|(_,Zero)=>Zero,(Positive,Positive)|(Negative,Negative)=>Positive,(Positive,Negative)|(Negative,Positive)=>Negative,}}}impl Neg for Sign{type Output=Sign;fn neg(self)->Sign{match self{Zero=>Zero,Positive=>Negative,Negative=>Positive,}}}#[derive(Clone,Eq,PartialEq)]pub struct BigIInt{pub sign:Sign,pub num:BigUInt,}impl BigIInt{pub fn zero()->Self{Self{sign:Zero,num:BigUInt::zero(),}}pub fn one()->Self{Self{sign:Positive,num:BigUInt::one(),}}pub fn is_zero(&self)->bool{self.sign==Zero}pub fn is_positive(&self)->bool{self.sign==Positive}pub fn is_negative(&self)->bool{self.sign==Negative}pub fn abs(&self)->Self{Self{sign:if self.is_zero(){Zero}else{Positive},num:self.num.clone(),}}fn add_assign_impl(&mut self,rhs:&Self){match(self.sign,rhs.sign){(Zero,_)=>{self.sign=rhs.sign;self.num=rhs.num.clone();}(_,Zero)=>{}(Positive,Positive)=>{self.num.add_assign_impl(&rhs.num);}(Negative,Negative)=>{self.num.add_assign_impl(&rhs.num);}(Positive,Negative)=>match self.num.cmp(&rhs.num){Greater=>{self.num.saturating_sub_assign_impl(&rhs.num);}Less=>{self.sign=Negative;self.num=rhs.num.saturating_sub_impl(&self.num);}Equal=>{*self=Self::zero();}},(Negative,Positive)=>match self.num.cmp(&rhs.num){Greater=>{self.num.saturating_sub_assign_impl(&rhs.num);}Less=>{self.sign=Positive;self.num=rhs.num.saturating_sub_impl(&self.num);}Equal=>{*self=Self::zero();}},}}fn sub_assign_impl(&mut self,rhs:&Self){match(self.sign,rhs.sign){(Zero,_)=>{self.sign=-rhs.sign;self.num=rhs.num.clone();}(_,Zero)=>{}(Positive,Positive)=>match self.num.cmp(&rhs.num){Greater=>{self.num.saturating_sub_assign_impl(&rhs.num);}Less=>{self.sign=Negative;self.num=rhs.num.saturating_sub_impl(&self.num);}Equal=>{*self=Self::zero();}},(Negative,Negative)=>match self.num.cmp(&rhs.num){Greater=>{self.sign=Negative;self.num=self.num.saturating_sub_impl(&rhs.num);}Less=>{self.sign=Positive;self.num=rhs.num.saturating_sub_impl(&self.num);}Equal=>{*self=Self::zero();}},(Positive,Negative)=>{self.num.add_assign_impl(&rhs.num);}(Negative,Positive)=>{self.num.add_assign_impl(&rhs.num);}}}pub fn checked_div_rem_trunc(&self,rhs:&Self)->Option<(Self,Self)>{if rhs.is_zero(){return None;}if self.is_zero(){return Some((Self::zero(),Self::zero()));}let(q_data,r_data)=self.num.checked_div_rem(&rhs.num)?;Some((if q_data.is_zero(){Self::zero()}else{Self{sign:&self.sign*&rhs.sign,num:q_data,}},if r_data.is_zero(){Self::zero()}else{Self{sign:self.sign,num:r_data,}},))}pub fn checked_div_rem_floor(&self,rhs:&Self)->Option<(Self,Self)>{let(mut q,mut r)=self.checked_div_rem_trunc(rhs)?;if!r.is_zero()&&(r.is_positive()!=rhs.is_positive()){q=&q-&BigIInt::one();r=&r+rhs;}Some((q,r))}pub fn checked_div_rem_euclid(&self,rhs:&Self)->Option<(Self,Self)>{let(mut q,mut r)=self.checked_div_rem_trunc(rhs)?;if r.is_negative(){if rhs.is_positive(){q.sub_assign(&BigIInt::one());r.add_assign(&rhs.abs());}else{q.add_assign(&BigIInt::one());r.sub_assign(&rhs.abs());}}Some((q,r))}pub fn gcd(&self,rhs:&Self)->Self{let(mut a,mut b)=(self.abs(),rhs.abs());while!b.is_zero(){a=&a%&b;mem::swap(&mut a,&mut b);}a}}impl Default for BigIInt{fn default()->Self{Self::zero()}}impl fmt::Debug for BigIInt{fn fmt(&self,f:&mut fmt::Formatter<'_>)->fmt::Result{match self.sign{Negative=>write!(f,"-{:?}",self.num),Zero=>write!(f,"0"),Positive=>write!(f,"{:?}",self.num),}}}impl fmt::Display for BigIInt{fn fmt(&self,f:&mut fmt::Formatter<'_>)->fmt::Result{match self.sign{Negative=>write!(f,"-{}",self.num),Zero=>write!(f,"0"),Positive=>write!(f,"{}",self.num),}}}impl From<u64>for BigIInt{fn from(x:u64)->Self{match x{0=>BigIInt::zero(),_=>BigIInt{sign:Positive,num:BigUInt::from(x),},}}}impl From<u128>for BigIInt{fn from(x:u128)->Self{match x{0=>BigIInt::zero(),_=>BigIInt{sign:Positive,num:BigUInt::from(x),},}}}impl From<i64>for BigIInt{fn from(x:i64)->Self{match x{0=>BigIInt::zero(),n if n>0=>BigIInt{sign:Positive,num:BigUInt::from(n.unsigned_abs()),},n=>BigIInt{sign:Negative,num:BigUInt::from(n.unsigned_abs()),},}}}impl From<i128>for BigIInt{fn from(x:i128)->Self{match x{0=>BigIInt::zero(),n if n>0=>BigIInt{sign:Positive,num:BigUInt::from(n.unsigned_abs()),},n=>BigIInt{sign:Negative,num:BigUInt::from(n.unsigned_abs()),},}}}impl Neg for&BigIInt{type Output=BigIInt;fn neg(self)->BigIInt{match self.sign{Zero=>self.clone(),sign=>BigIInt{sign:-sign,num:self.num.clone(),},}}}impl Add for&BigIInt{type Output=BigIInt;fn add(self,rhs:&BigIInt)->BigIInt{let mut v=self.clone();v.add_assign_impl(rhs);v}}impl Sub for&BigIInt{type Output=BigIInt;fn sub(self,rhs:&BigIInt)->BigIInt{let mut v=self.clone();v.sub_assign_impl(rhs);v}}impl Mul for&BigIInt{type Output=BigIInt;fn mul(self,rhs:&BigIInt)->BigIInt{if self.is_zero()||rhs.is_zero(){return BigIInt::zero();}BigIInt{sign:&self.sign*&rhs.sign,num:&self.num*&rhs.num,}}}impl Div for&BigIInt{type Output=BigIInt;fn div(self,rhs:&BigIInt)->BigIInt{self.checked_div_rem_trunc(rhs).expect(ERRMSG_DIVIDE_BY_ZERO).0}}impl Rem for&BigIInt{type Output=BigIInt;fn rem(self,rhs:&BigIInt)->BigIInt{self.checked_div_rem_trunc(rhs).expect(ERRMSG_DIVIDE_BY_ZERO).1}}impl Shl<u32>for&BigIInt{type Output=BigIInt;fn shl(self,bits:u32)->BigIInt{BigIInt{sign:self.sign,num:self.num.shl(bits),}}}impl Shr<u32>for&BigIInt{type Output=BigIInt;fn shr(self,bits:u32)->BigIInt{let v=self.num.shr(bits);if v.is_zero(){BigIInt::zero()}else{BigIInt{sign:self.sign,num:self.num.shr(bits),}}}}impl Add<u64>for&BigIInt{type Output=BigIInt;fn add(self,rhs:u64)->BigIInt{let mut v=self.clone();v.add_assign(rhs);v}}impl Sub<u64>for&BigIInt{type Output=BigIInt;fn sub(self,rhs:u64)->BigIInt{let mut v=self.clone();v.sub_assign(rhs);v}}impl AddAssign<&BigIInt>for BigIInt{fn add_assign(&mut self,rhs:&BigIInt){self.add_assign_impl(rhs);}}impl SubAssign<&BigIInt>for BigIInt{fn sub_assign(&mut self,rhs:&BigIInt){self.sub_assign_impl(rhs);}}impl MulAssign<&BigIInt>for BigIInt{fn mul_assign(&mut self,rhs:&BigIInt){*self=(&*self).mul(rhs);}}impl DivAssign<&BigIInt>for BigIInt{fn div_assign(&mut self,rhs:&BigIInt){*self=(&*self).div(rhs);}}impl RemAssign<&BigIInt>for BigIInt{fn rem_assign(&mut self,rhs:&BigIInt){*self=(&*self).rem(rhs);}}impl AddAssign<u64>for BigIInt{fn add_assign(&mut self,rhs:u64){if rhs==0{return;}if self.is_negative(){match self.num.cmp_u64(rhs){Greater=>{self.num=&self.num-rhs;}Less=>{self.sign=Positive;self.num=&BigUInt::from(rhs)-&self.num;}Equal=>{*self=BigIInt::zero();}}}else{self.num+=rhs;self.sign=Positive;}}}impl SubAssign<u64>for BigIInt{fn sub_assign(&mut self,rhs:u64){if rhs==0{return;}if self.is_positive(){match self.num.cmp_u64(rhs){Greater=>{self.num-=rhs;}Less=>{self.sign=Negative;self.num=&BigUInt::from(rhs)-&self.num;}Equal=>{*self=BigIInt::zero();}}}else{self.num+=rhs;self.sign=Negative;}}}impl MulAssign<u64>for BigIInt{fn mul_assign(&mut self,rhs:u64){if self.is_zero(){return;}if rhs==0{*self=BigIInt::zero();return;}self.num.mul_assign_small(rhs);}}impl DivAssign<u64>for BigIInt{fn div_assign(&mut self,rhs:u64){if rhs==0{panic!("{}",ERRMSG_DIVIDE_BY_ZERO);}if self.is_zero(){return;}let(q,_)=self.num.checked_div_rem_small(rhs).unwrap();if q.is_zero(){*self=BigIInt::zero();}else{self.num=q;}}}impl RemAssign<u64>for BigIInt{fn rem_assign(&mut self,rhs:u64){if rhs==0{panic!("{}",ERRMSG_DIVIDE_BY_ZERO);}if self.is_zero(){return;}let(_,r)=self.num.checked_div_rem_small(rhs).unwrap();if r==0{*self=BigIInt::zero();}else{self.num=BigUInt::from(r);}}}impl str::FromStr for BigIInt{type Err=&'static str;fn from_str(s:&str)->Result<Self,Self::Err>{let s=s.trim();if s.starts_with('-'){let num=BigUInt::from_dec_str(&s[1..].trim())?;if num.is_zero(){Ok(BigIInt::zero())}else{Ok(BigIInt{sign:Negative,num,})}}else if s.starts_with('+'){let num=BigUInt::from_dec_str(&s[1..].trim())?;if num.is_zero(){Ok(BigIInt::zero())}else{Ok(BigIInt{sign:Positive,num,})}}else{let num=BigUInt::from_dec_str(s)?;if num.is_zero(){Ok(BigIInt::zero())}else{Ok(BigIInt{sign:Positive,num,})}}}}impl Ord for BigIInt{fn cmp(&self,rhs:&Self)->Ordering{match(self.sign,rhs.sign){(Negative,Positive)=>Less,(Positive,Negative)=>Greater,(Zero,Zero)=>Equal,(Zero,Positive)=>Less,(Zero,Negative)=>Greater,(Positive,Zero)=>Greater,(Negative,Zero)=>Less,(Positive,Positive)=>self.num.cmp(&rhs.num),(Negative,Negative)=>rhs.num.cmp(&self.num),}}}impl PartialOrd for BigIInt{fn partial_cmp(&self,rhs:&Self)->Option<Ordering>{Some(self.cmp(rhs))}}impl Neg for BigIInt{type Output=BigIInt;fn neg(self)->BigIInt{(&self).neg()}}use self::Sign::*;use std::{cmp::Ordering::{self,*},fmt,mem,ops::{Add,AddAssign,BitAnd,BitAndAssign,BitOr,BitOrAssign,BitXor,BitXorAssign,Div,DivAssign,Mul,MulAssign,Neg,Rem,RemAssign,Shl,Shr,Sub,SubAssign,},str,};const DEC_BASE:u64=10u64.pow(19);const ERRMSG_EMPTY_STRING:&str="empty string";const ERRMSG_INVALID_CHAR:&str="invalid character in decimal string";const ERRMSG_UNDERFLOW:&str="underflow occurred";const ERRMSG_DIVIDE_BY_ZERO:&str="divide by zero";}
#[rustfmt::skip]pub mod input_lite{#[macro_export]macro_rules!read_value{($b:expr,($($t:tt),*))=>{($(read_value!($b,$t)),*)};($b:expr,[$t:tt;$len:expr])=>{(0..$len).map(|_|read_value!($b,$t)).collect::<Vec<_>>()};($b:expr,byte)=>{token($b,|s|s[0])};($b:expr,Bytes)=>{token($b,|s|s.to_vec())};($b:expr,Chars)=>{token($b,|s|std::str::from_utf8(s).unwrap().chars().collect::<Vec<_>>())};($b:expr,usize1)=>{read_value!($b,usize)-1};($b:expr,$t:ty)=>{token($b,|s|std::str::from_utf8(s).unwrap().parse::<$t>().unwrap())};}#[macro_export]macro_rules!input_inner{($b:expr)=>{};($b:expr,)=>{};($b:expr,$var:ident:$t:tt$($r:tt)*)=>{let$var=read_value!($b,$t);input_inner!{$b$($r)*}};}#[macro_export]macro_rules!input{(source=$s:expr,$($r:tt)*)=>{input_inner!{$s,$($r)*}};($($r:tt)*)=>{let mut i=std::io::stdin().lock();input_inner!{&mut i,$($r)*}std::mem::drop(i);};}pub fn token<R:std::io::BufRead,T>(r:&mut R,f:impl Fn(&[u8])->T)->T{let(b,mut l)=loop{let b=r.fill_buf().unwrap();assert!(!b.is_empty());if let Some(p)=b.iter().position(|&b|!b.is_ascii_whitespace()){break(&b[p..],p);}let l=b.len();r.consume(l);};if let Some(p)=b.iter().position(|&b|b.is_ascii_whitespace()){let t=&b[..p];let x=f(t);r.consume(l+p+1);return x;}l+=b.len();let mut t=b.to_vec();r.consume(l);while let Ok(b)=r.fill_buf(){if b.is_empty(){break;}if let Some(p)=b.iter().position(|&b|b.is_ascii_whitespace()){t.extend_from_slice(&b[..p]);r.consume(p+1);break;}let l=b.len();t.extend_from_slice(b);r.consume(l);}f(&t)}}
0