Submission #47260683

---

Source Code Expand

#![allow(dead_code)]

pub use __cargo_equip::prelude::*;

use std::{cmp::Reverse, collections::BinaryHeap};

use minimal_lib_range::lazysegtree::{LazyOpSegTree, LazySegOps};
use proconio::marker::Usize1;

pub enum O {}

impl LazySegOps for O {
    type Value = i64;
    type Action = i64;

    fn doubling_action(level: usize, action: Self::Action) -> Self::Action {
        action
    }

    fn concat(level: usize, left: Self::Value, right: Self::Value) -> Self::Value {
        left.max(right)
    }

    fn action(level: usize, action: Self::Action, value: Self::Value) -> Self::Value {
        action + value
    }

    fn action_mul(lhs: Self::Action, rhs: Self::Action) -> Self::Action {
        lhs + rhs
    }
}

fn main() {
    proconio::input! {
        n: usize,
        d: usize,
        w: usize,
        mut tx: [(Usize1, Usize1); n]
    }
    tx.sort();
    let mut apples: BinaryHeap<Reverse<(usize, usize)>> = BinaryHeap::new();
    let mut seg: LazyOpSegTree<i64, i64, O> = LazyOpSegTree::new(400000);
    let mut mx = 0;

    for i in 0..n {
        let (t, x) = tx[i];
        while let Some(Reverse(a)) = apples.pop() {
            if a.0 + d <= t {
                seg.range_apply(a.1, a.1 + w, -1);
            } else {
                apples.push(Reverse(a));
                break;
            }
        }
        seg.range_apply(x, x + w, 1);
        apples.push(Reverse((t, x)));

        mx = mx.max(seg.range_sum(0, 200001));
    }
    println!("{}", mx);
}

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

///  # Bundled libraries
/// 
///  - `minimal-lib-algo 0.1.0 (path+██████████████████████████████████)`   published in **missing** licensed under **missing** as `crate::__cargo_equip::crates::minimal_lib_algo`
///  - `minimal-lib-int 0.2.0 (path+█████████████████████████████████)`     published in **missing** licensed under **missing** as `crate::__cargo_equip::crates::minimal_lib_int`
///  - `minimal-lib-range 0.1.0 (path+███████████████████████████████████)` published in **missing** licensed under **missing** as `crate::__cargo_equip::crates::minimal_lib_range`
#[cfg_attr(any(), rustfmt::skip)]
#[allow(unused)]
mod __cargo_equip {
    pub(crate) mod crates {
        pub mod minimal_lib_algo {pub mod bisect{use std::ops::{Add,Shr};use std::cmp::PartialOrd;pub fn bisect_predicate_max<T>(mut f:impl FnMut(T)->bool,l:T,r:T)->Option<T>where T:Add<T,Output=T>+Shr<T,Output=T>+PartialOrd+From<i64>+Copy,{let one=1.into();let mut unchanged=true;let mut l=l;let mut r=r+one;while(l+one)<r{let h=(l+r)>>one;if f(h){unchanged=false;l=h;}else{r=h;}}if unchanged&&!f(l){return None;}Some(l)}pub fn bisect_predicate_min<T>(mut f:impl FnMut(T)->bool,l:T,r:T)->Option<T>where T:Add<T,Output=T>+Shr<T,Output=T>+PartialOrd+From<i64>+Copy,{let one=1.into();let mut unchanged=true;let mut l=l;let mut r=r;if!f(r){return None;}while(l+one)<r{let h=(l+r)>>one;if f(h){r=h;}else{unchanged=false;l=h;}}if unchanged&&f(l){return Some(l);}Some(r)}}pub mod compress{use std::{collections::{BTreeMap,HashMap},hash::Hash,};pub struct Compress<T:Hash+Eq+Ord+Clone>{count:usize,vec:Vec<T>,to_index:HashMap<T,usize>,}impl<T:Hash+Eq+Ord+Clone>Compress<T>{pub fn new(it:&[T])->Compress<T>{let mut count=0;let mut last=None;let mut to_index=HashMap::new();let mut vec=vec![];let mut s=it.to_vec();s.sort();for x in s.into_iter(){if let Some(y)=last.take(){if y==x{continue;}}to_index.insert(x.clone(),count);vec.push(x.clone());count+=1;last=Some(x);}Self{count,vec,to_index,}}pub fn is_empty(&self)->bool{self.count==0}pub fn len(&self)->usize{self.count}pub fn get_index(&self,value:T)->usize{self.to_index[&value]}pub fn invert(&self,index:usize)->T{self.vec[index].clone()}}#[derive(Debug)]pub struct SegmentCompress<T:Hash+Eq+Ord+Clone>{count:usize,vec:Vec<T>,to_index:BTreeMap<T,usize>,}impl<T:Hash+Eq+Ord+Clone>SegmentCompress<T>{pub fn new<'a>(it:&[T])->Self{let mut count=0;let mut last=None;let mut to_index=BTreeMap::new();let mut vec=vec![];let mut s=it.to_vec();s.sort();for x in s.into_iter(){if let Some(y)=last.take(){if y==x{last=Some(y);continue;}}to_index.insert(x.clone(),count);vec.push(x.clone());count+=1;last=Some(x);}Self{count,vec,to_index,}}pub fn len(&self)->usize{self.count}pub fn get_index(&self,value:T)->usize{self.to_index[&value]}pub fn get_range(&self,left:T,right:T)->Option<(usize,usize)>{let mut rn=self.to_index.range(left.clone()..right.clone());let mut rn2=self.to_index.range(left..right);Some((*rn.next()?.1,*rn2.next_back()?.1))}pub fn invert(&self,index:usize)->T{self.vec[index].clone()}}}pub mod runlength{pub fn runlength<T>(xs:&[T])->Vec<(T,usize)>where T:Eq+Clone,{let mut result=vec![];let mut run=1;let mut prev_index=0;for(index,item)in xs.iter().enumerate().skip(1){if item==&xs[prev_index]{run+=1;}else{result.push((xs[prev_index].clone(),run));prev_index=index;run=1;}}result.push((xs[prev_index].clone(),run));result}}pub mod uf{pub struct UnionFind{vec:Vec<usize>,component_size:Vec<usize>,}impl UnionFind{pub fn new(size:usize)->Self{let mut vec=Vec::new();let mut component_size=Vec::new();for i in 0..size{vec.push(i);component_size.push(1);}Self{vec,component_size,}}pub fn find_root(&mut self,a:usize)->usize{let mut a=a;let mut stack=Vec::new();loop{let parent=self.vec[a];if parent==a{for i in stack{self.vec[i]=a;}return a;}else{stack.push(a);a=parent;}}}pub fn union(&mut self,a:usize,b:usize){let a_root=self.find_root(a);let b_root=self.find_root(b);if a_root!=b_root{self.vec[a_root]=b_root;self.component_size[b_root]+=self.component_size[a_root];self.component_size[a_root]=0;}}pub fn is_unioned(&mut self,a:usize,b:usize)->bool{self.find_root(a)==self.find_root(b)}}pub trait Group:Default{fn mul(&self,rhs:&Self)->Self;fn inv(&self)->Self;}#[derive(Debug)]pub struct UnionFindWith<T:Group>{vec:Vec<(usize,T)>,component_size:Vec<usize>,}impl<T:Group+Copy+std::fmt::Debug>UnionFindWith<T>{pub fn new(size:usize)->Self{let mut vec=Vec::new();let mut component_size=Vec::new();for i in 0..size{vec.push((i,T::default()));component_size.push(1);}Self{vec,component_size,}}pub fn find_root(&mut self,a:usize)->(usize,T){let mut a=a;let mut accum=T::default();let mut stack:Vec<(usize,T)> =Vec::new();loop{let(parent,g)=&self.vec[a];if*parent==a{stack.push((a,accum));let root_accum=accum;for(i,g)in stack.into_iter(){let nx=accum.mul(&g.inv());self.vec[i]=(a,nx);}return(a,root_accum);}else{stack.push((a,accum));accum=accum.mul(g);a=*parent;}}}pub fn union(&mut self,a:usize,b:usize,g:T){let(a_root,ga)=self.find_root(a);let(b_root,gb)=self.find_root(b);if a_root!=b_root{self.vec[a_root]=(b_root,g.mul(&gb.mul(&ga.inv())));self.component_size[b_root]+=self.component_size[a_root];self.component_size[a_root]=0;}}pub fn is_unioned(&mut self,a:usize,b:usize)->Option<T>{let(ra,ga)=self.find_root(a);let(rb,gb)=self.find_root(b);if ra==rb{Some(ga.mul(&gb.inv()))}else{None}}}}pub mod monotone_minima{pub struct MonotoneMinima<'a,T:Ord>{rows:usize,columns:usize,func:Box<dyn 'a+Fn(usize,usize)->T>}impl<'a,T:Ord>MonotoneMinima<'a,T>{pub fn new(rows:usize,columns:usize,func:Box<dyn 'a+Fn(usize,usize)->T>)->Self{Self{rows,columns,func}}fn minima_recur(&self,result:&mut[usize],yl:usize,yr:usize,xl:usize,xr:usize){if yl==yr{return;}let mid=(yl+yr)/2;let mut pos=xl;let mut minimum_value=(self.func)(mid,xl);for i in(xl+1)..xr{let v=(self.func)(mid,i);if v<minimum_value{minimum_value=v;pos=i;}}result[mid]=pos;self.minima_recur(result,yl,mid,xl,pos+1,);self.minima_recur(result,mid+1,yr,pos,xr,);}pub fn minimas(&self)->Vec<usize>{let mut result=vec![0;self.rows];self.minima_recur(&mut result,0,self.rows,0,self.columns);result}}}pub mod interval_set{use std::collections::BTreeMap;#[derive(Debug,Clone,Default)]pub struct IntervalSet<T>where T:Ord+Copy{s:BTreeMap<T,T>,}impl<T>IntervalSet<T>where T:Ord+Copy{pub fn new()->Self{Self{s:BTreeMap::new()}}pub fn get(&self,x:T)->Option<(T,T)>{use std::ops::Bound::*;self.s.range((Unbounded,Included(x))).next_back().filter(|&(_l,r)|x<*r).map(|(x,y)|(*x,*y))}pub fn insert(&mut self,l:T,r:T){use std::ops::Bound::*;let(l,r)=if let Some((il,ir))=self.s.range_mut((Unbounded,Included(l))).next_back(){if l<=*ir{if*ir<r{*ir=r;}(*il,*ir)}else{self.s.insert(l,r);(l,r)}}else{self.s.insert(l,r);(l,r)};while let Some((il,ir))=self.s.range((Unbounded,Included(r))).next_back(){let il=*il;let ir=*ir;if l==il{break;}let cur_seg_r=self.s.get_mut(&l).unwrap();if r<ir{*cur_seg_r=ir;}self.s.remove(&il);}}pub fn remove(&mut self,l:T,r:T){use std::ops::Bound::*;if let Some((_il,ir))=self.s.range_mut((Unbounded,Included(r))).next_back(){if r<*ir{let t=*ir;*ir=l;self.s.insert(r,t);}else if l<*ir{*ir=l;}};while let Some((il,ir))=self.s.range((Included(l),Excluded(r))).next(){let il=*il;let ir=*ir;let cur_seg_r=self.s.get_mut(&il).unwrap();if l<ir{*cur_seg_r=r;}self.s.remove(&il);}if let Some((_il,ir))=self.s.range_mut((Unbounded,Included(l))).next_back(){if l<*ir{*ir=l;}};}pub fn intervals(&self)->Vec<(T,T)>{self.s.iter().map(|(x,y)|(*x,*y)).collect()}pub fn intersect(&mut self,l:T,r:T){use std::ops::Bound::*;while let Some((il,ir))=self.s.range((Unbounded,Excluded(l))).next(){let il=*il;let ir=*ir;self.s.remove(&il);if l<ir{self.s.insert(l,ir);}}while let Some((il,_ir))=self.s.range((Included(r),Unbounded)).next(){let il=*il;self.s.remove(&il);}if let Some((_il,ir))=self.s.range_mut((Unbounded,Included(r))).next_back(){if r<*ir{let _t=*ir;*ir=r;}};}pub fn append(&mut self,new:&Self){for(l,r)in new.intervals().into_iter(){self.insert(l,r);}}}}pub mod permutation{pub fn inverse_permutation(perm:&[usize])->Vec<usize>{let n=perm.len();let mut res=vec![0;n];for i in 0..n{res[perm[i]]=i;}res}pub fn composite_permutation(first:&[usize],second:&[usize])->Vec<usize>{debug_assert_eq!(first.len(),second.len());let n=first.len();let mut res=vec![0;n];for i in 0..n{res[i]=second[first[i]];}res}}pub mod trisect{use std::cmp::PartialOrd;use std::ops::{Add,Div,Sub};pub fn trisect_predicate_min<T,S>(mut f:impl FnMut(T)->S,l:T,r:T)->(T,S)where T:Add<T,Output=T>+Sub<T,Output=T>+Div<T,Output=T>+PartialOrd+From<i64>+Copy+From<i64>+std::fmt::Debug,S:Ord+Clone,{let one=1.into();let two=2.into();let three:T=3.into();let mut l=l;let mut r=r+one;while(l+two)<r{let h1=(l+l+r+one)/three;let h2=(l+r+r)/three;eprintln!("{:?} {:?} {:?} {:?}",l,h1,h2,r);assert!(l<h1);assert!(h1<h2);assert!(h2<r);let cmp=Ord::cmp(&f(h1),&f(h2));match cmp{std::cmp::Ordering::Less=>{r=h2;}std::cmp::Ordering::Equal=>{l=h1;r=h2;}std::cmp::Ordering::Greater=>{l=h1;}}}let mut c=vec![];while l<r{c.push((l,f(l)));l=l+one;}c.into_iter().min_by_key(|x|x.1.clone()).unwrap()}}}
        pub mod minimal_lib_int {use crate::__cargo_equip::preludes::minimal_lib_int::*;pub mod cache{use crate::__cargo_equip::preludes::minimal_lib_int::*;mod mul{use crate::__cargo_equip::preludes::minimal_lib_int::*;pub struct MulCache{pub accum:Vec<i64>,pub inv:Vec<i64>,pub accum_inv:Vec<i64>,pub n:usize,pub p:i64,}impl MulCache{pub fn new(p:i64,n:usize)->Self{let mut accum=vec![0;n];let mut inv=vec![0;n];let mut accum_inv=vec![0;n];accum[0]=1;accum[1]=1;inv[0]=0;inv[1]=1;accum_inv[0]=1;accum_inv[1]=1;for i in 2..n{let i=i as i64;accum[i as usize]=(accum[(i-1)as usize]*i)%p;inv[i as usize]=p-inv[(p%i)as usize]*(p/i)%p;accum_inv[i as usize]=(accum_inv[(i-1)as usize]*inv[i as usize])%p;}Self{accum,inv,accum_inv,n,p,}}pub fn extend(&mut self,n:usize){if self.n<n{let p=self.p;for i in self.n..n{let i=i as i64;self.accum.push((self.accum[(i-1)as usize]*i)%p);self.inv.push(p-self.inv[(p%i)as usize]*(p/i)%p);self.accum_inv.push((self.accum_inv[(i-1)as usize]*self.inv[i as usize])%p);}self.n=n;}}pub fn inv_fact(&self,n:i64)->i64{self.accum_inv[n as usize]}pub fn combin(&self,n:i64,k:i64)->i64{debug_assert!(n<self.n as i64);if n<0||k<0||n<k{return 0;}self.accum[n as usize]*(self.accum_inv[k as usize]*self.accum_inv[(n-k)as usize]%self.p)%self.p}}}mod fft{use crate::__cargo_equip::preludes::minimal_lib_int::*;use crate::__cargo_equip::crates::minimal_lib_int::utils::{powmod,modinv,minimum_exponent};pub struct FFTCache{pub modulo:i64,pub g:i64,pub sum_e:Vec<i64>,pub sum_ie:Vec<i64>,pub montg_r:i64,pub montg_r1:i64,pub montg_r2:i64,pub montg_r3:i64,pub montg_rinv:i64,pub montg_ndash:i64,}impl FFTCache{fn primitive_root(m:i64)->i64{match m{2=>1,167772161=>3,469762049=>3,595591169=>3,645922817=>3,897581057=>3,998244353=>3,754974721=>11,_=>todo!(),}}pub fn new(m:i64)->Self{let primroot=Self::primitive_root(m);let mut es=vec![0;30];let mut ies=vec![0;30];let cnt2=(m-1).trailing_zeros()as usize;let mut e=powmod(primroot,(m-1)>>cnt2,m);let mut ie=modinv(e,m);for i in(2..=cnt2).rev(){es[i-2]=e;ies[i-2]=ie;e*=e;e%=m;ie*=ie;ie%=m;}let sum_e:Vec<i64> =es.iter().scan(1,|acc,e|{*acc*=e;*acc%=m;Some(*acc)}).collect();let sum_ie:Vec<i64> =ies.iter().scan(1,|acc,ie|{*acc*=ie;*acc%=m;Some(*acc)}).collect();let rex=minimum_exponent(m);let montg_r=1<<rex;let montg_r1=montg_r%m;let montg_r2=(montg_r1*montg_r1)%m;let montg_r3=(montg_r2*montg_r1)%m;let montg_rinv=modinv(montg_r1%m,m);let mut montg_ndash=0;{let mut temp=0;for i in 0..rex{if(temp&1)==0{temp+=m;montg_ndash+=1<<i;}temp>>=1;}}debug_assert_eq!((m*montg_ndash)%montg_r,montg_r-1);Self{modulo:m,g:primroot,sum_e,sum_ie,montg_r,montg_r1,montg_r2,montg_r3,montg_rinv,montg_ndash,}}}}pub use mul::MulCache;pub use fft::FFTCache;}pub mod utils{use crate::__cargo_equip::preludes::minimal_lib_int::*;mod gcd{use crate::__cargo_equip::preludes::minimal_lib_int::*;pub fn gcd(a:i64,b:i64)->i64{let t=(a|b).trailing_zeros();let mut a=a;let mut b=b;a>>=t;b>>=t;if a&1==1{std::mem::swap(&mut a,&mut b);}a>>=a.trailing_zeros();while a!=b{if a>b{a-=b;a>>=a.trailing_zeros();}else{b-=a;b>>=b.trailing_zeros();}}a<<t}pub fn modinv(a:i64,b:i64)->i64{if b==2{return a;}let m=b;let mut a=a;let mut b=b;let mut u=1;let mut v=0;while a>0{if a&1==0{a>>=1;if u&1==0{u>>=1;}else{u+=m;u>>=1;}}else{if a<b{std::mem::swap(&mut a,&mut b);std::mem::swap(&mut u,&mut v);}a=(a-b)>>1;u-=v;if u<0{u+=m;}if u&1==0{u>>=1;}else{u+=m;u>>=1;}}}assert_eq!(b,1);v}pub fn modinv_u64(a:u64,b:u64)->u64{if b==2{return a;}let m=b;let mut a=a;let mut b=b;let mut u=1;let mut v=0;while a>0{if a&1==0{a>>=1;if u&1==0{u>>=1;}else{u+=m;u>>=1;}}else{if a<b{std::mem::swap(&mut a,&mut b);std::mem::swap(&mut u,&mut v);}a=(a-b)>>1;if u<v{u+=m;}u-=v;if u&1==0{u>>=1;}else{u+=m;u>>=1;}}}assert_eq!(b,1);v}}mod modulo{use crate::__cargo_equip::preludes::minimal_lib_int::*;use super::gcd::modinv;pub fn powmod_large(val:i64,rhs:i64,m:i64)->i64{if rhs<0{todo!()}let mut res=1_i128;let mut r=rhs as i128;let mut a=val as i128;let m=m as i128;while r>0{if r&1==1{res*=a;res%=m;}a*=a;a%=m;r>>=1;}res as i64}pub fn powmod(val:i64,rhs:i64,m:i64)->i64{if rhs<0{return modinv(powmod(val,-rhs,m),m);}let mut res=1;let mut r=rhs;let mut a=val;while r>0{if r&1==1{res*=a;res%=m;}a*=a;a%=m;r>>=1;}res}pub fn sqrt_mod(y:i64,p:i64)->Option<i64>{let y=y%p;if p==2{return Some(y);}if y==0{return Some(0);}let q=p-1;let m=q.trailing_zeros();let q=q>>m;if powmod(y,q<<(m-1),p)==p-1{return None;}let mut z=2;while powmod(z,q<<(m-1),p)!=p-1{z+=1;}let mut t=powmod(y,q,p);let mut x=powmod(y,(q+1)>>1,p);let mut u=powmod(z,q,p);if m>=2{for i in(0..=(m-2)).rev(){if powmod(t,1<<i,p)==p-1{t*=(u*u)%p;t%=p;x*=u;x%=p;}u*=u;u%=p;}}if x>p-x{x=p-x;}Some(x)}}mod util{use crate::__cargo_equip::preludes::minimal_lib_int::*;use minimal_lib_algo::bisect::bisect_predicate_max;pub fn isqrt(x:i64)->i64{bisect_predicate_max(|y|y*y<=x,0,x.min(1<<31)).unwrap()}pub fn i_kth_root(x:i64,k:i64)->i64{if x<=1{return x;}if k==1{return x;}let bs=63-x.leading_zeros();bisect_predicate_max(|y|{y.checked_pow(k as u32).map(|yk|yk<=x).unwrap_or_default()},1,x>>(bs-bs/k as u32-1),).unwrap()as _}pub fn digits(x:i64,base:i64)->Vec<i64>{if x==0{return vec![0];}let mut res=vec![];let mut t=x;while t>0{res.push(t%base);t/=base;}res.reverse();res}pub fn minimum_exponent(n:i64)->usize{(64-n.saturating_sub(1).leading_zeros())as _}}mod prelude{use crate::__cargo_equip::preludes::minimal_lib_int::*;pub use super::gcd::{modinv,modinv_u64,gcd};pub use super::modulo::{powmod,powmod_large,sqrt_mod};pub use super::util::{digits,i_kth_root,isqrt,minimum_exponent};pub use super::gerner::{gerner,gerner_u64_batch,gerner_batch};}mod gerner{use crate::__cargo_equip::preludes::minimal_lib_int::*;use crate::__cargo_equip::crates::minimal_lib_int::utils::modinv;fn ex_euclid(a:i64,b:i64)->(i64,i64,i64){let mut a=a;let mut b=b;let mut c=1;let mut d=0;let mut e=0;let mut f=1;while a!=0{let q=b/a;let res=(b%a,a,d,c-d*q,f,e-f*q);a=res.0;b=res.1;c=res.2;d=res.3;e=res.4;f=res.5;}if b<0{e=-e;c=-c;b=-b;}(e,c,b)}fn modular_div(n:i64,m:i64,p:i64)->Option<i64>{let(e,_c,b)=ex_euclid(m,p);if n%b!=0{None}else{let q=(n/b)*e;let mut q=q%p;if q<0{q+=p;}Some(q)}}pub fn gerner(r:&[i64],m:&[i64],mm:i64)->Option<i64>{debug_assert_eq!(r.len(),m.len());let l=m.len();let mut cons=vec![0;l];let mut coeff=vec![1;l];let mut res=0;let mut r_coeff=1;for i in 0..l{let mut v=modular_div(r[i]-cons[i],coeff[i],m[i])?;if v<0{v+=m[i];}for j in i+1..l{cons[j]+=v*coeff[j];cons[j]%=m[j];coeff[j]*=m[i];coeff[j]%=m[j];}res=(res+v*r_coeff)%mm;r_coeff=(r_coeff*m[i])%mm;}Some(res)}pub fn gerner_batch(r:&[Vec<i64>],m:&[i64],mm:i64)->Vec<i64>{debug_assert_eq!(r.len(),m.len());let rl=r[0].len();let l=m.len();let mut cons=vec![vec![0i64;rl];l];let mut coeff=vec![1;l];let mut res=vec![0i64;rl];let mut r_coeff=1;for i in 0..l{let d=modinv(coeff[i],m[i]);let v:Vec<i64> =r[i].iter().zip(cons[i].iter()).map(|(&x,&c)|{let mut v=(x-c)*d;v%=m[i];if v<0{v+=m[i];}v}).collect();for j in i+1..l{cons[j].iter_mut().zip(v.iter()).for_each(|(c,&v)|{*c+=v*coeff[j];*c%=m[j];});coeff[j]*=m[i];coeff[j]%=m[j];}res.iter_mut().zip(v.iter()).for_each(|(r,&v)|{*r+=v*r_coeff;*r%=mm;});r_coeff=(r_coeff*m[i])%mm;}res}pub fn gerner_u64_batch(r:&[Vec<u64>])->Vec<u64>{debug_assert!(r.len()<=5);let rl=r[0].len();let mut cons=[vec![0;rl],vec![0;rl],vec![0;rl],vec![0;rl],vec![0;rl]];let m=[469762049,595591169,645922817,897581057,998244353];let coeff=[[1,1,1,1,1],[1,469762049,469762049,469762049,469762049],[1,469762049,44993443,300657119,491473740],[1,469762049,44993443,528892613,173461320],[1,469762049,44993443,528892613,202041274],];let coeff_inv=[1,436766862,35884648,19245542,390741676];let mut res=vec![0u64;rl];let mut r_coeff:u64=1;for i in 0..r.len(){let v:Vec<u64> =r[i].iter().zip(cons[i].iter()).map(|(&x,&c)|{let mut v=if x<c{x+m[i]-c}else{x-c};v*=coeff_inv[i];v%=m[i];v}).collect();for j in(i+1)..r.len(){cons[j].iter_mut().zip(v.iter()).for_each(|(c,&v)|{*c=(*c).wrapping_add(v.wrapping_mul(coeff[i][j]));*c%=m[j];});}res.iter_mut().zip(v.iter()).for_each(|(r,&v)|{*r=r.wrapping_add(v.wrapping_mul(r_coeff));});r_coeff=r_coeff.wrapping_mul(m[i]);}res}}pub use prelude::*;}pub mod modulo{use crate::__cargo_equip::preludes::minimal_lib_int::*;mod modulo_v2{use crate::__cargo_equip::preludes::minimal_lib_int::*;use std::{ops::{Add,AddAssign,Div,DivAssign,Mul,MulAssign,Neg,Sub,SubAssign},marker::PhantomData,thread::LocalKey,usize,cell::RefCell};use crate::__cargo_equip::crates::minimal_lib_int::{utils::{powmod,modinv},cache::{MulCache,FFTCache}};use super::{Mod998244353,Mod1000000007};pub trait Field:Sized+Clone+Add<Self,Output=Self>+Sub<Self,Output=Self>+Neg<Output=Self>+Mul<Self,Output=Self>+Div<Self,Output=Self>{fn pow(self,rhs:i64)->Self;fn inv(self)->Self;fn zero()->Self;fn one()->Self;}pub trait Modulus:'static+Copy+Eq+Ord{const IS_PRIME:bool=false;fn mul_cache()->&'static LocalKey<RefCell<MulCache>>;fn convolution(x:&[ModInt<Self>],y:&[ModInt<Self>])->Vec<ModInt<Self>>;fn get_modulo()->i64;fn extend(n:usize){Self::mul_cache().with(|cache|cache.borrow_mut().extend(n));}}pub trait FFTModulus:Modulus{const EXP:usize;fn fft_cache()->&'static LocalKey<RefCell<FFTCache>>;}pub type ModInt998244353=ModInt<Mod998244353>;pub type ModInt1000000007=ModInt<Mod1000000007>;#[derive(Copy,Clone,Eq,PartialEq,PartialOrd,Ord)]#[repr(transparent)]pub struct ModInt<T:Modulus>{pub v:i64,ph:PhantomData<fn()->T>}impl<T:Modulus>std::fmt::Debug for ModInt<T>{fn fmt(&self,f:&mut std::fmt::Formatter<'_>)->std::fmt::Result{f.write_fmt(format_args!("{}",self.v))}}impl<T:Modulus>std::fmt::Display for ModInt<T>{fn fmt(&self,f:&mut std::fmt::Formatter<'_>)->std::fmt::Result{f.write_fmt(format_args!("{}",self.v))}}impl<T:Modulus>ModInt<T>{pub fn pow(self,rhs:i64)->Self{Self::new(powmod(self.v,rhs,T::get_modulo()))}pub fn inv(self)->Self{Self::new(modinv(self.v,T::get_modulo()))}pub fn zero()->Self{Self::new(0)}pub fn one()->Self{Self::new(1)}pub fn fact(n:usize)->Self{T::mul_cache().with(|cache|{let cache=cache.borrow();let accum=&cache.accum;Self::from(accum[n])})}pub fn combin(n:usize,k:usize)->Self{T::mul_cache().with(|cache|{let cache=cache.borrow();Self::from(cache.combin(n as i64,k as i64))})}pub fn factinv(n:usize)->Self{T::mul_cache().with(|cache|{let cache=cache.borrow();let accum_inv=&cache.accum_inv;Self::from(accum_inv[n])})}}impl<T:Modulus>Field for ModInt<T>{fn pow(self,rhs:i64)->Self{Self::new(powmod(self.v,rhs,T::get_modulo()))}fn inv(self)->Self{Self::new(modinv(self.v,T::get_modulo()))}fn zero()->Self{Self::new(0)}fn one()->Self{Self::new(1)}}impl<T:Modulus>AsRef<ModInt<T>>for ModInt<T>{fn as_ref(&self)->&ModInt<T>{self}}impl<T:Modulus>Default for ModInt<T>{fn default()->Self{Self{v:0,ph:Default::default()}}}impl<T:Modulus>Add<Self>for ModInt<T>{type Output=Self;fn add(self,rhs:Self)->Self::Output{let r=self.v+rhs.v;if r>=T::get_modulo(){Self::new(r-T::get_modulo())}else{Self::new(r)}}}impl<T:Modulus>Sub<Self>for ModInt<T>{type Output=Self;fn sub(self,rhs:Self)->Self::Output{let r=self.v-rhs.v;if r<0{Self::new(r+T::get_modulo())}else{Self::new(r)}}}impl<T:Modulus>Mul<Self>for ModInt<T>{type Output=Self;fn mul(self,rhs:Self)->Self::Output{Self::new(self.v*rhs.v%T::get_modulo())}}impl<T:Modulus>Div<Self>for ModInt<T>{type Output=Self;fn div(self,rhs:Self)->Self::Output{self*rhs.inv()}}impl<T:Modulus>Neg for ModInt<T>{type Output=Self;fn neg(self)->Self{Self::new(if self.v!=0{T::get_modulo()-self.v}else{0})}}impl<T:Modulus>std::iter::Sum for ModInt<T>{fn sum<I:Iterator<Item=Self>>(iter:I)->Self{let mut acc=0;for x in iter.into_iter(){acc+=x.v;}acc%=T::get_modulo();Self::new(acc)}}impl<T:Modulus>AddAssign for ModInt<T>{fn add_assign(&mut self,rhs:Self){self.v+=rhs.v;if self.v>=T::get_modulo(){self.v-=T::get_modulo();}}}impl<T:Modulus>SubAssign for ModInt<T>{fn sub_assign(&mut self,rhs:Self){self.v-=rhs.v;if self.v<0{self.v+=T::get_modulo();}}}impl<T:Modulus>MulAssign for ModInt<T>{fn mul_assign(&mut self,rhs:Self){self.v*=rhs.v;self.v%=T::get_modulo();}}impl<T:Modulus>DivAssign for ModInt<T>{fn div_assign(&mut self,rhs:Self){self.v*=rhs.inv().v;self.v%=T::get_modulo();}}impl<T:Modulus>ModInt<T>{pub fn new(v:i64)->Self{debug_assert!(0<=v&&v<T::get_modulo());Self{v,ph:PhantomData}}}impl<T:Modulus>From<i32>for ModInt<T>{fn from(x:i32)->Self{let x=x as _;if x<0{ModInt::new(x%T::get_modulo()+T::get_modulo())}else if x<T::get_modulo(){ModInt::new(x)}else{ModInt::new(x%T::get_modulo())}}}impl<T:Modulus>From<i64>for ModInt<T>{fn from(x:i64)->Self{if x<0{ModInt::new(x%T::get_modulo()+T::get_modulo())}else if x<T::get_modulo(){ModInt::new(x)}else{ModInt::new(x%T::get_modulo())}}}impl<T:Modulus>From<usize>for ModInt<T>{fn from(x:usize)->Self{if(x as i64)<T::get_modulo(){ModInt::new(x as i64)}else{ModInt::new(x as i64%T::get_modulo())}}}impl<T:Modulus>From<ModInt<T>>for i64{fn from(x:ModInt<T>)->Self{x.v}}impl<T:Modulus>From<ModInt<T>>for usize{fn from(x:ModInt<T>)->Self{x.v as _}}impl<T:Modulus>From<ModInt<T>>for i32{fn from(x:ModInt<T>)->Self{x.v as _}}}mod modulos{use crate::__cargo_equip::preludes::minimal_lib_int::*;use std::{thread::LocalKey,cell::RefCell};use crate::__cargo_equip::crates::minimal_lib_int::{cache::{FFTCache,MulCache},fft::{modint_fft::convol,convol_u64::convol_modint}};use super::{FFTModulus,ModInt,Modulus};macro_rules!gen_static_modulo{($x:ident,$modulo:literal,$fft_exp:literal)=>{#[derive(Debug,Copy,Clone,Ord,PartialOrd,Eq,PartialEq)]pub enum$x{}impl$x{thread_local!{static MUL_CACHE:RefCell<MulCache> =RefCell::new(MulCache::new($modulo,1000005));static FFT_CACHE:RefCell<FFTCache> =RefCell::new(FFTCache::new($modulo));}}impl FFTModulus for$x{const EXP:usize=$fft_exp;fn fft_cache()->&'static LocalKey<RefCell<FFTCache>>{&Self::FFT_CACHE}}impl Modulus for$x{fn get_modulo()->i64{$modulo}const IS_PRIME:bool=true;fn mul_cache()->&'static LocalKey<RefCell<MulCache>>{&Self::MUL_CACHE}fn convolution(x:&[ModInt<Self>],y:&[ModInt<Self>])->Vec<ModInt<Self>>{convol(x,y)}}};($x:ident,$modulo:literal)=>{#[derive(Debug,Copy,Clone,Ord,PartialOrd,Eq,PartialEq)]pub enum$x{}impl$x{thread_local!{static MUL_CACHE:RefCell<MulCache> =RefCell::new(MulCache::new($modulo,1000005));}}impl Modulus for$x{fn get_modulo()->i64{$modulo}const IS_PRIME:bool=true;fn mul_cache()->&'static LocalKey<RefCell<MulCache>>{&Self::MUL_CACHE}fn convolution(x:&[ModInt<Self>],y:&[ModInt<Self>])->Vec<ModInt<Self>>{convol_modint(&x,&y)}}};}gen_static_modulo!{Mod469762049,469762049_i64,26}gen_static_modulo!{Mod595591169,595591169_i64,23}gen_static_modulo!{Mod645922817,645922817_i64,23}gen_static_modulo!{Mod998244353,998244353_i64,23}gen_static_modulo!{Mod1000000007,1000000007_i64}#[derive(Debug,Copy,Clone,Ord,PartialOrd,Eq,PartialEq)]pub enum ModDynamic{}impl ModDynamic{thread_local!{static DYNAMIC_MODULO:RefCell<i64> =RefCell::new(1000000007);static MUL_CACHE:RefCell<MulCache> =RefCell::new(MulCache::new(1000000007_i64,5));}pub fn set_modulo(new_modulo:i64){Self::DYNAMIC_MODULO.with(|x|{*x.borrow_mut()=new_modulo;});Self::MUL_CACHE.with(|x|{*x.borrow_mut()=MulCache::new(new_modulo,5);});}}impl Modulus for ModDynamic{fn get_modulo()->i64{Self::DYNAMIC_MODULO.with(|x|{let x=*x.borrow();x})}const IS_PRIME:bool=true;fn mul_cache()->&'static LocalKey<RefCell<MulCache>>{&Self::MUL_CACHE}fn convolution(x:&[ModInt<Self>],y:&[ModInt<Self>])->Vec<ModInt<Self>>{convol_modint(x,y)}}}pub use modulo_v2::{FFTModulus,Field,ModInt,Modulus};pub use modulos::{Mod1000000007,Mod998244353,Mod469762049,Mod595591169,Mod645922817,ModDynamic};}pub mod fft{use crate::__cargo_equip::preludes::minimal_lib_int::*;pub mod modint_fft{use crate::__cargo_equip::preludes::minimal_lib_int::*;use crate::__cargo_equip::crates::minimal_lib_int::{modulo::{ModInt,FFTModulus},utils::minimum_exponent,};pub fn fft<T:FFTModulus>(v:&mut[ModInt<T>]){let n=v.len();let h=64-n.saturating_sub(1).leading_zeros();T::fft_cache().with(|cache|{let cache=cache.borrow();let sum_e=&cache.sum_e;for ph in 1..=h{let w=1<<(ph-1);let p=1<<(h-ph);let mut now=ModInt::one();for s in 0..w{let offset=s<<(h-ph+1);for i in offset..(p+offset){let l=v[i];let r=v[i+p]*now;v[i]=l+r;v[i+p]=l-r;}now*=ModInt::new(sum_e[(!s).trailing_zeros()as usize]);}}});}pub fn ifft<T:FFTModulus>(v:&mut[ModInt<T>]){let n=v.len();let h=64-n.saturating_sub(1).leading_zeros();T::fft_cache().with(|cache|{let cache=cache.borrow();let sum_ie=&cache.sum_ie;for ph in(1..=h).rev(){let w=1<<(ph-1);let p=1<<(h-ph);let mut inow=ModInt::one();for s in 0..w{let offset=s<<(h-ph+1);for i in 0..p{let l=v[i+offset];let r=v[i+offset+p];v[i+offset]=l+r;v[i+offset+p]=(l-r)*inow;}inow*=ModInt::new(sum_ie[(!s).trailing_zeros()as usize]);}}});}pub fn convol<T:FFTModulus>(x:&[ModInt<T>],y:&[ModInt<T>])->Vec<ModInt<T>>{if x.is_empty()||y.is_empty(){return vec![];}let(xl,yl)=(x.len(),y.len());if std::cmp::min(xl,yl)<=60{let(xl,yl,a,b)=if xl<yl{(yl,xl,y,x)}else{(xl,yl,x,y)};let mut ans=vec![ModInt::zero();xl+yl-1];for i in 0..xl{for j in 0..yl{ans[i+j]+=a[i]*b[j];}}return ans;}let zl=xl+yl-1;let(mut x,mut y)=(x.to_owned(),y.to_owned());let z=1<<minimum_exponent(zl as _);x.resize(z,ModInt::zero());fft(&mut x);y.resize(z,ModInt::zero());fft(&mut y);for i in 0..z{x[i]*=y[i];}ifft(&mut x);x.resize(zl,ModInt::zero());let iz=ModInt::from(z as i64).inv();for i in 0..zl{x[i]*=iz;}x}pub fn convol_in<T:FFTModulus>(x:&mut[ModInt<T>],y:&[ModInt<T>]){if x.is_empty()||y.is_empty(){return;}let(xl,yl)=(x.len(),y.len());if std::cmp::min(xl,yl)<=60{let mut ans=vec![ModInt::zero();xl];for i in 0..xl{for j in 0..yl{if i+j>=xl{break;}ans[i+j]+=x[i]*y[j];}}x.clone_from_slice(&ans[0..xl]);return;}let mut y=y.to_owned();fft(x);fft(&mut y);for i in 0..xl{x[i]*=y[i];}ifft(x);let iz=ModInt::from(xl as i64).inv();for i in 0..xl{x[i]*=iz;}}}pub mod relax_mult{use crate::__cargo_equip::preludes::minimal_lib_int::*;use crate::__cargo_equip::crates::minimal_lib_int::modulo::{ModInt,Modulus};use std::collections::VecDeque;const BITS:usize=64;pub struct RelaxedMul<T:Modulus>{index:usize,left:Vec<ModInt<T>>,right:Vec<ModInt<T>>,convolved:Vec<VecDeque<Vec<ModInt<T>>>>,}impl<T:Modulus>RelaxedMul<T>{pub fn new()->Self{RelaxedMul{index:0,left:Vec::new(),right:Vec::new(),convolved:vec![VecDeque::new();32],}}fn block_conv(&self,left:usize,right:usize,block_size:usize)->Vec<ModInt<T>>{let l=&self.left[left..left+block_size];let r=&self.right[right..right+block_size];T::convolution(l,r)}pub fn push(&mut self,left:ModInt<T>,right:ModInt<T>)->ModInt<T>{let mut block_type=(self.index+2)&(self.index+2).wrapping_neg();let index=self.index;self.left.push(left);self.right.push(right);if block_type>self.index{block_type>>=1;if block_type>1{for i in 1..BITS{let block_size=(1<<i)as usize;if block_size>=block_type{let block_min=block_size-1;let b=self.block_conv(block_min,block_min,block_size);self.convolved[i].push_back(b);break;}let block_min1=self.index+1-block_size;let block_min2=block_size-1;let b1=self.block_conv(block_min1,block_min2,block_size);let b2=self.block_conv(block_min2,block_min1,block_size);self.convolved[i].push_back(b1);self.convolved[i].push_back(b2);}}}else if block_type>1{for i in 1..BITS{let block_size=(1<<i)as usize;if block_size>block_type{break;}let block_min1=self.index+1-block_size;let block_min2=block_size-1;let b1=self.block_conv(block_min1,block_min2,block_size);let b2=self.block_conv(block_min2,block_min1,block_size);self.convolved[i].push_back(b1);self.convolved[i].push_back(b2);}}let mut sum=if index>0{left*self.right[0]+right*self.left[0]}else{left*right};for i in 1..BITS{while self.convolved[i].len()>4{self.convolved[i].pop_front();}let q=(index+2)%(1<<i);match self.convolved[i].len(){0=>{break;}1=>{sum+=self.convolved[i][0][q];}3=>{if q<(1<<i)-1{sum+=self.convolved[i][0][q+(1<<i)];}sum+=self.convolved[i][1][q];sum+=self.convolved[i][2][q];}4=>{if q<(1<<i)-1{sum+=self.convolved[i][0][q+(1<<i)];sum+=self.convolved[i][1][q+(1<<i)];}sum+=self.convolved[i][2][q];sum+=self.convolved[i][3][q];}_=>todo!(),}}self.index+=1;sum}}}pub mod convol_u64{use crate::__cargo_equip::preludes::minimal_lib_int::*;use crate::__cargo_equip::crates::minimal_lib_int::fft::modint_fft::convol;use crate::__cargo_equip::crates::minimal_lib_int::modulo::{ModInt,Modulus,Mod469762049,Mod595591169,Mod645922817};use crate::__cargo_equip::crates::minimal_lib_int::{cache::FFTCache,utils::modinv_u64,utils::minimum_exponent,};use crate::__cargo_equip::crates::minimal_lib_int::utils::{gerner,gerner_batch,gerner_u64_batch};pub fn fft_mod_u64(v:&mut[u64],cache:&FFTCache){let n=v.len();let h=64-n.saturating_sub(1).leading_zeros();let FFTCache{sum_e,modulo,..}=cache;let modulo=*modulo as u64;for ph in 1..=h{let w=1<<(ph-1);let p=1<<(h-ph);let mut now=1;for s in 0..w{let offset=s<<(h-ph+1);for i in offset..(p+offset){let l=v[i];let mut r=v[i+p]*now;r%=modulo;v[i]=l+r;if v[i]>modulo{v[i]-=modulo;}if l>r{v[i+p]=l-r;}else{v[i+p]=(modulo+l)-r;}}now*=sum_e[(!s).trailing_zeros()as usize]as u64;now%=modulo;}}}pub fn ifft_mod_u64(v:&mut[u64],cache:&FFTCache){let n=v.len();let h=64-n.saturating_sub(1).leading_zeros();let FFTCache{sum_ie,modulo,..}=cache;let modulo=*modulo as u64;for ph in(1..=h).rev(){let w=1<<(ph-1);let p=1<<(h-ph);let mut inow=1;for s in 0..w{let offset=s<<(h-ph+1);for i in 0..p{let l=v[i+offset];let r=v[i+offset+p];v[i+offset]=l+r;if v[i+offset]>modulo{v[i+offset]-=modulo;}let q=if l>r{l-r}else{(modulo+l)-r};v[i+offset+p]=(q*inow)%modulo;}inow*=sum_ie[(!s).trailing_zeros()as usize]as u64;inow%=modulo;}}}pub fn convol_mod(x:&[u64],y:&[u64],cache:&FFTCache)->Vec<u64>{if x.is_empty()||y.is_empty(){return vec![];}let(xl,yl)=(x.len(),y.len());let zl:usize=xl+yl-1;let(mut x,mut y)=(x.to_owned(),y.to_owned());let z=1<<minimum_exponent(zl as _);let modulo=cache.modulo as u64;for i in 0..xl{x[i]%=modulo;}for i in 0..yl{y[i]%=modulo;}x.resize(z,0);fft_mod_u64(&mut x,cache);y.resize(z,0);fft_mod_u64(&mut y,cache);for(x,y)in x.iter_mut().zip(y.into_iter()){*x*=y;*x%=modulo;}ifft_mod_u64(&mut x,cache);x.resize(zl,0);let iz=modinv_u64(z as u64,modulo);for x in x.iter_mut(){*x*=iz;*x%=modulo;}x}thread_local!{pub static MODULO_CACHES:Box<[FFTCache;5]> =Box::new([FFTCache::new(469762049),FFTCache::new(595591169),FFTCache::new(645922817),FFTCache::new(897581057),FFTCache::new(998244353)]);}pub fn convol_u64(x:&[u64],y:&[u64])->Vec<u64>{let(xl,yl)=(x.len(),y.len());if std::cmp::min(xl,yl)<=60{let(xl,yl,a,b)=if xl<yl{(yl,xl,y,x)}else{(xl,yl,x,y)};let mut ans:Vec<u64> =vec![0;xl+yl-1];for i in 0..xl{for j in 0..yl{ans[i+j]=ans[i+j].wrapping_add(a[i].wrapping_mul(b[j]));}}return ans;}MODULO_CACHES.with(|cc|{let[c1,c2,c3,c4,c5]=cc.as_ref();let z1=convol_mod(x,y,c1);let z2=convol_mod(x,y,c2);let z3=convol_mod(x,y,c3);let z4=convol_mod(x,y,c4);let z5=convol_mod(x,y,c5);gerner_u64_batch(&[z1,z2,z3,z4,z5])})}pub fn convol_u32(x:&[u64],y:&[u64])->Vec<u64>{let(xl,yl)=(x.len(),y.len());if std::cmp::min(xl,yl)<=60{let(xl,yl,a,b)=if xl<yl{(yl,xl,y,x)}else{(xl,yl,x,y)};let mut ans:Vec<u64> =vec![0;xl+yl-1];for i in 0..xl{for j in 0..yl{ans[i+j]=ans[i+j].wrapping_add(a[i].wrapping_mul(b[j]));}}return ans;}MODULO_CACHES.with(|cc|{let[c1,c2,c3,_c4,_c5]=cc.as_ref();let z1=convol_mod(x,y,c1);let z2=convol_mod(x,y,c2);let z3=convol_mod(x,y,c3);let mut result=vec![];let m=[c1.modulo,c2.modulo,c3.modulo];for i in 0..z1.len(){result.push(gerner(&[z1[i]as i64,z2[i]as i64,z3[i]as i64],&m,1000000007).unwrap()as u64)}result})}pub fn convol_modint<T:Modulus>(x:&[ModInt<T>],y:&[ModInt<T>])->Vec<ModInt<T>>{let(xl,yl)=(x.len(),y.len());if std::cmp::min(xl,yl)<=60{let(xl,yl,a,b)=if xl<yl{(yl,xl,y,x)}else{(xl,yl,x,y)};let mut ans:Vec<_> =vec![ModInt::zero();xl+yl-1];for i in 0..xl{for j in 0..yl{ans[i+j]+=a[i]*b[j];}}return ans;}MODULO_CACHES.with(|cc|{let[c1,c2,c3,_c4,_c5]=cc.as_ref();let z1:Vec<i64> ={let x:Vec<ModInt<Mod469762049>> =x.iter().map(|&i|i64::from(i).into()).collect();let y:Vec<ModInt<Mod469762049>> =y.iter().map(|&i|i64::from(i).into()).collect();convol(&x,&y).into_iter().map(|x|x.v).collect()};let z2:Vec<i64> ={let x:Vec<ModInt<Mod595591169>> =x.iter().map(|&i|i64::from(i).into()).collect();let y:Vec<ModInt<Mod595591169>> =y.iter().map(|&i|i64::from(i).into()).collect();convol(&x,&y).into_iter().map(|x|x.v).collect()};let z3:Vec<i64> ={let x:Vec<ModInt<Mod645922817>> =x.iter().map(|&i|i64::from(i).into()).collect();let y:Vec<ModInt<Mod645922817>> =y.iter().map(|&i|i64::from(i).into()).collect();convol(&x,&y).into_iter().map(|x|x.v).collect()};let m=[c1.modulo,c2.modulo,c3.modulo];let r=gerner_batch(&[z1,z2,z3],&m,T::get_modulo()).into_iter().map(|x|x.into()).collect();r})}}pub mod subset_convolution{use crate::__cargo_equip::preludes::minimal_lib_int::*;use std::ops::{AddAssign,SubAssign,MulAssign,Mul};pub fn lower_moebius<T:AddAssign+SubAssign+Copy>(v:&mut[T]){let n=v.len();let h=n.trailing_zeros();for j in 0..h{let p=1<<j;let mut i=n-1;while i>=p{if i&p>0{v[i]-=v[i^p];i-=1;}else{i-=p;}}}}pub fn lower_zeta<T:AddAssign+SubAssign+Copy>(v:&mut[T]){let n=v.len();let h=n.trailing_zeros();for j in 0..h{let p=1<<j;let mut i=0;while i<n{if i&p==0{v[i^p]+=v[i];i+=1;}else{i+=p;}}}}pub fn upper_zeta<T:AddAssign+SubAssign+Copy>(v:&mut[T]){let n=v.len();let h=n.trailing_zeros();for j in 0..h{let p=1<<j;let mut i=n-1;while i>=p{if i&p>0{v[i^p]+=v[i];i-=1;}else{i-=p;}}}}pub fn upper_moebius<T:AddAssign+SubAssign+Copy>(v:&mut[T]){let n=v.len();let h=n.trailing_zeros();for j in 0..h{let p=1<<j;let mut i=0;while i<n{if i&p==0{v[i]-=v[i^p];i+=1;}else{i+=p;}}}}pub fn subset_convolution<T:AddAssign+SubAssign+MulAssign+Mul<Output=T>+Default+Copy>(n:usize,a:&[T],b:&[T])->Vec<T>{let mut rank_a=vec![vec![Default::default();1<<n];n+1];let mut rank_b=vec![vec![Default::default();1<<n];n+1];for i in 0..(1<<n)as usize{rank_a[i.count_ones()as usize][i]=a[i];rank_b[i.count_ones()as usize][i]=b[i];}for i in 0..=n{lower_zeta(&mut rank_a[i]);lower_zeta(&mut rank_b[i]);}for i in(0..=n).rev(){rank_a[i].iter_mut().zip(rank_b[0].iter()).for_each(|(x,y)|*x*=*y);let(rank_a,ri)=rank_a.split_at_mut(i);for j in 1..=i{ri[0].iter_mut().zip(rank_a[i-j].iter().zip(rank_b[j].iter())).for_each(|(x,(y,z))|*x+=*y**z);}}for i in 0..=n{lower_moebius(&mut rank_a[i]);}let mut res=Vec::with_capacity(1<<n);for i in 0..(1<<n)as usize{res.push(rank_a[i.count_ones()as usize][i]);}res}}pub mod divisor_zeta{use crate::__cargo_equip::preludes::minimal_lib_int::*;use crate::__cargo_equip::crates::minimal_lib_int::modulo::{ModInt,Modulus};pub fn lower_divisor_zeta<T:Modulus>(v:&mut[ModInt<T>]){let n=v.len();let mut s=vec![false;n];for i in 2..n{if!s[i]{for(j,k)in(0..n).step_by(i).enumerate().skip(1){s[k]=true;v[k]+=v[j];}}}}pub fn lower_divisor_moebius<T:Modulus>(v:&mut[ModInt<T>]){let n=v.len();let mut s=vec![false;n];for i in 2..n{if!s[i]{for(j,k)in(0..n).step_by(i).enumerate().skip(1).rev(){s[k]=true;v[k]-=v[j];}}}}pub fn upper_divisor_zeta<T:Modulus>(v:&mut[ModInt<T>]){let n=v.len();let mut s=vec![false;n];for i in 2..n{if!s[i]{for(j,k)in(0..n).step_by(i).enumerate().skip(1).rev(){s[k]=true;v[j]+=v[k];}}}}pub fn upper_divisor_moebius<T:Modulus>(v:&mut[ModInt<T>]){let n=v.len();let mut s=vec![false;n];for i in 2..n{if!s[i]{for(j,k)in(0..n).step_by(i).enumerate().skip(1){s[k]=true;v[j]-=v[k];}}}}}}}
        pub mod minimal_lib_range {use crate::__cargo_equip::preludes::minimal_lib_range::*;pub mod fenwick{use crate::__cargo_equip::preludes::minimal_lib_range::*;#[derive(Debug,Clone)]pub struct Fenwick{v:Vec<i64>,total:i64,}impl Fenwick{pub fn new(n:usize)->Self{Self{v:vec![0;n],total:0,}}pub fn new_from(v:&[i64])->Self{let mut v=Vec::from(v);let mut total=0;let n=v.len();for i in 0..n{total+=v[i];}for i in 1..32{if(1<<i)>n{break;}for j in(((1<<i)-1)..n).step_by(1<<i){v[j]+=v[j-(1<<(i-1))];}}Self{v,total,}}pub fn len(&self)->usize{self.v.len()}pub fn add(&mut self,i:usize,v:i64){let mut i=i+1;while i<=self.v.len(){self.v[i-1]+=v;i+=i&i.wrapping_neg();}self.total+=v;}pub fn left_sum_excluded(&self,i:usize)->i64{if i==0{0}else{self.left_sum(i-1)}}pub fn left_sum(&self,i:usize)->i64{if i>=self.v.len()-1{return self.total;}let mut i=i+1;let mut res=0;while i>0{res+=self.v[i-1];i-=i&i.wrapping_neg();}res}pub fn right_sum_excluded(&self,i:usize)->i64{self.total-self.left_sum(i)}pub fn right_sum(&self,i:usize)->i64{self.total-self.left_sum_excluded(i)}}}pub mod co_fenwick{use crate::__cargo_equip::preludes::minimal_lib_range::*;use crate::__cargo_equip::crates::minimal_lib_range::fenwick::Fenwick;#[derive(Debug,Clone)]pub struct CoFenwick{fenwick:Fenwick,}impl CoFenwick{pub fn new(n:usize)->Self{Self{fenwick:Fenwick::new(n),}}pub fn new_from(v:&[i64])->Self{let accum=v.iter().scan(0i64,|s,x|{let r=*x-*s;*s=*x;Some(r)}).collect::<Vec<i64>>();Self{fenwick:Fenwick::new_from(&accum),}}pub fn range_add(&mut self,v:i64,l:usize,r:usize){self.fenwick.add(l,v);if r<self.fenwick.len(){self.fenwick.add(r,-v);}}pub fn range_add_left(&mut self,v:i64,r:usize){self.fenwick.add(0,v);if r<self.fenwick.len(){self.fenwick.add(r,-v);}}pub fn get(&self,i:usize)->i64{self.fenwick.left_sum(i)}pub fn len(&self)->usize{self.fenwick.len()}}}pub mod lazysegtree{use crate::__cargo_equip::preludes::minimal_lib_range::*;use std::marker::PhantomData;pub trait LazySegOps{type Value:Default+Copy;type Action:Default+Copy;fn doubling_action(level:usize,action:Self::Action)->Self::Action;fn zero()->Self::Value{Default::default()}fn ident_action()->Self::Action where Self::Action:Default,{Default::default()}fn concat(level:usize,left:Self::Value,right:Self::Value)->Self::Value;fn action(level:usize,action:Self::Action,value:Self::Value)->Self::Value;fn action_mul(lhs:Self::Action,rhs:Self::Action)->Self::Action;}pub struct LazyOpSegTree<T,A,O>where T:Default+Copy,A:Default+Copy,O:LazySegOps<Action=A>,{exponent:usize,len:usize,pub vec:Vec<T>,pub lazy:Vec<A>,_dummy:PhantomData<fn()->O>,}impl<T,A,O>LazyOpSegTree<T,A,O>where T:Default+Copy,A:Default+Copy,O:LazySegOps<Value=T,Action=A>,{pub fn new(size:usize)->Self{let mut exponent=0;for i in 0..32{if size<=(1<<i){exponent=i;break;}}Self{exponent,len:size,vec:vec![O::zero();1<<(exponent+1)],lazy:vec![O::ident_action();1<<(exponent+1)],_dummy:PhantomData,}}pub fn set_unpropagated(&mut self,index:usize,value:T){let index=(1<<self.exponent)-1+index;self.vec[index]=value;}pub fn put(&mut self,index:usize,value:T){let mut index=(1<<self.exponent)-1+index;self.vec[index]=value;index=(index-1)>>1;for i in 1..=self.exponent{self.vec[index]=O::concat(i,self.vec[index*2+1],self.vec[index*2+2]);if i<self.exponent{index=(index-1)>>1;}}}pub fn propagate(&mut self){for i in 1..=self.exponent{let base=(1<<(self.exponent-i))-1;for j in 0..(self.len>>i){let node=base+j;self.vec[node]=O::concat(i,self.vec[node*2+1],self.vec[node*2+2]);}if(self.len>>(i-1))&1>0{let node=base+(self.len>>i);self.vec[node]=self.vec[node*2+1];}}}fn eval(&mut self,node:usize,node_level:usize,node_left:usize,node_right:usize){let added_val=O::doubling_action(node_level,self.lazy[node]);self.vec[node]=O::action(node_level,added_val,self.vec[node]);if node_right-node_left>1{self.lazy[node*2+1]=O::action_mul(self.lazy[node],self.lazy[node*2+1]);self.lazy[node*2+2]=O::action_mul(self.lazy[node],self.lazy[node*2+2]);}self.lazy[node]=O::ident_action();}fn sub_range_apply(&mut self,node:usize,node_level:usize,node_left:usize,node_right:usize,left:usize,right:usize,action:A,)->T{self.eval(node,node_level,node_left,node_right);if node_right<=left||right<=node_left{O::zero()}else if left<=node_left&&node_right<=right{self.lazy[node]=action;self.eval(node,node_level,node_left,node_right);self.vec[node]}else{let mid=(node_left+node_right)>>1;self.sub_range_apply(node*2+1,node_level-1,node_left,mid,left,right,action,);self.sub_range_apply(node*2+2,node_level-1,mid,node_right,left,right,action,);self.vec[node]=O::concat(node_level-1,self.vec[node*2+1],self.vec[node*2+2],);self.vec[node]}}pub fn range_apply(&mut self,left:usize,right:usize,action:A){self.sub_range_apply(0,self.exponent,0,1<<self.exponent,left,right,action);}fn sub_range_sum(&mut self,node:usize,node_level:usize,node_left:usize,node_right:usize,left:usize,right:usize,)->T{self.eval(node,node_level,node_left,node_right);if node_right<=left||right<=node_left{O::zero()}else if left<=node_left&&node_right<=right{self.vec[node]}else{let mid=(node_left+node_right)/2;let left_val=self.sub_range_sum(node*2+1,node_level-1,node_left,mid,left,right);let right_val=self.sub_range_sum(node*2+2,node_level-1,mid,node_right,left,right);O::concat(node_level-1,left_val,right_val)}}pub fn range_sum(&mut self,left:usize,right:usize)->T{self.sub_range_sum(0,self.exponent,0,1<<self.exponent,left,right)}}}pub mod sparse_table{use crate::__cargo_equip::preludes::minimal_lib_range::*;pub struct MinSparseTable<T>where T:Default+Copy+Ord,{pub vec:Vec<T>,pub jump_table:Vec<T>,pub exponent:usize,pub size:usize,}impl<T>From<Vec<T>>for MinSparseTable<T>where T:Default+Copy+Ord,{fn from(v:Vec<T>)->Self{let mut st=Self::new(v.len());st.vec.clone_from(&v);st.update_table();st}}impl<T>MinSparseTable<T>where T:Default+Copy+Ord,{pub fn new(size:usize)->Self{let mut exponent=0;for i in 0..32{if size<(1<<i){exponent=i;break;}}MinSparseTable{vec:vec![Default::default();size],jump_table:vec![Default::default();size*exponent],exponent,size,}}pub fn update_table(&mut self){for i in 0..self.size{self.jump_table[i]=self.vec[i];}for i in 0..(self.exponent-1){for j in 0..=(self.size-(1<<(i+1))){self.jump_table[(i+1)*self.size+j]=Ord::min(self.jump_table[i*self.size+j],self.jump_table[i*self.size+j+(1<<i)],);}}}pub fn rmq(&self,l:usize,r:usize)->T{if l>=r{panic!("expected l < r, but l={}, r={}",l,r);}let width=r-l;let exp=0usize.leading_zeros()-width.leading_zeros();let exp=(exp-1)as usize;Ord::min(self.jump_table[exp*self.size+l],self.jump_table[exp*self.size+r-(1<<exp)],)}}}pub mod segtreebeat{use crate::__cargo_equip::preludes::minimal_lib_range::*;use std::fmt::Display;pub trait LazySegBeatsOps:Default{type Action:Default;fn doubling_action(level:usize,action:Self::Action)->Self::Action;fn zero()->Self{Default::default()}fn ident_action()->Self::Action where Self::Action:Default,{Default::default()}fn concat(level:usize,left:Self,right:Self)->Self;fn action(level:usize,action:Self::Action,value:Self)->Option<Self>;fn action_mul(lhs:Self::Action,rhs:Self::Action)->Self::Action;}#[derive(Debug,Clone,Default,Copy,Eq,PartialEq,PartialOrd,Ord)]pub struct MyAction{chmax:Option<i64>,chmin:Option<i64>,add:i64,}#[derive(Debug,Clone,Copy)]pub struct MyValue<T>{value:T,max:T,min:T,max_pop:usize,min_pop:usize,scd_max:T,scd_min:T,}impl Default for MyValue<i64>{fn default()->Self{Self{value:0,max:std::i64::MIN>>2,min:std::i64::MAX>>2,max_pop:0,min_pop:0,scd_max:std::i64::MIN>>2,scd_min:std::i64::MAX>>2,}}}impl From<i64>for MyValue<i64>{fn from(x:i64)->Self{Self::new(x)}}impl Display for MyValue<i64>{fn fmt(&self,f:&mut std::fmt::Formatter<'_>)->std::fmt::Result{f.write_fmt(format_args!("{} ({}[{}],{},{},{}[{}])",self.value,self.min,self.min_pop,self.scd_min,self.scd_max,self.max,self.max_pop))}}impl<T>MyValue<T>where T:Ord+Eq+std::ops::Add<Output=T>+std::ops::Sub<Output=T>+Copy,{fn new(value:T)->Self{Self{value,max:value,min:value,max_pop:1,min_pop:1,scd_max:value,scd_min:value,}}}impl LazySegBeatsOps for MyValue<i64>{type Action=MyAction;fn doubling_action(_level:usize,action:Self::Action)->Self::Action{action}fn concat(_level:usize,lhs:Self,rhs:Self)->Self{let(max,max_pop,scd_max)=if lhs.max==rhs.max{(lhs.max,lhs.max_pop+rhs.max_pop,lhs.scd_max.max(rhs.scd_max),)}else if lhs.max>rhs.max{if lhs.scd_max<lhs.max{(lhs.max,lhs.max_pop,lhs.scd_max.max(rhs.max))}else{(lhs.max,lhs.max_pop,rhs.max)}}else if rhs.scd_max<rhs.max{(rhs.max,rhs.max_pop,lhs.max.max(rhs.scd_max))}else{(rhs.max,rhs.max_pop,lhs.max)};let(min,min_pop,scd_min)=if lhs.min==rhs.min{(lhs.min,lhs.min_pop+rhs.min_pop,lhs.scd_min.min(rhs.scd_min),)}else if lhs.min<rhs.min{if lhs.scd_min>lhs.min{(lhs.min,lhs.min_pop,lhs.scd_min.min(rhs.min))}else{(lhs.min,lhs.min_pop,rhs.min)}}else if rhs.scd_min>rhs.min{(rhs.min,rhs.min_pop,lhs.min.min(rhs.scd_min))}else{(rhs.min,rhs.min_pop,lhs.min)};Self{value:lhs.value+rhs.value,max,min,max_pop,min_pop,scd_max,scd_min,}}fn action(level:usize,action:Self::Action,value:Self)->Option<Self>{let value=if let Some(action)=action.chmin{if action<=value.min{MyValue{value:action<<level,min:action,max:action,scd_max:std::i64::MIN>>2,scd_min:std::i64::MAX>>2,max_pop:1<<level,min_pop:1<<level,}}else if action>=value.max{value}else if action>=value.scd_max{MyValue{value:value.value+-(value.max_pop as i64)*(value.max-action),max:action,scd_min:action.min(value.scd_min),..value}}else if level==0{MyValue::from(action)}else{return None;}}else{value};let value=if let Some(action)=action.chmax{if action>=value.max{MyValue{value:action<<level,min:action,max:action,scd_max:std::i64::MIN>>2,scd_min:std::i64::MAX>>2,max_pop:1<<level,min_pop:1<<level,}}else if action<=value.min{value}else if action<=value.scd_min{MyValue{value:value.value+value.min_pop as i64*(action-value.min),min:action,scd_max:action.max(value.scd_max),..value}}else if level==0{MyValue::from(action)}else{return None;}}else{value};Some(MyValue{value:value.value+(action.add<<level),max:value.max+action.add,min:value.min+action.add,scd_max:value.scd_max+action.add,scd_min:value.scd_min+action.add,..value})}fn action_mul(lhs:Self::Action,rhs:Self::Action)->Self::Action{let chmax=lhs.chmax.map(|x|(x-rhs.add));let chmin=lhs.chmin.map(|x|(x-rhs.add));MyAction{chmax:rhs.chmax.map(|x|{let x=chmin.map(|z|z.min(x)).unwrap_or(x);chmax.map(|y|x.max(y)).unwrap_or(x)}).or(chmax),chmin:rhs.chmin.map(|x|chmin.map(|y|x.min(y)).unwrap_or(x)).or(chmin),add:lhs.add+rhs.add,}}fn ident_action()->Self::Action where Self::Action:Default,{MyAction{chmax:None,chmin:None,add:0,}}}pub struct LazyOpSegBeatTree<T,A>where T:Default+Copy+LazySegBeatsOps<Action=A>,A:Default+Copy,{exponent:usize,len:usize,vec:Vec<T>,lazy:Vec<A>,}impl<T,A>LazyOpSegBeatTree<T,A>where T:Default+Copy+LazySegBeatsOps<Action=A>,A:Default+Copy,{fn new(size:usize)->Self{let mut exponent=0;for i in 0..32{if size<=(1<<i){exponent=i;break;}}Self{exponent,len:size,vec:vec![T::zero();1<<(exponent+1)],lazy:vec![T::ident_action();1<<(exponent+1)],}}fn set(&mut self,index:usize,value:T){let index=(1<<self.exponent)-1+index;self.vec[index]=value;}pub fn propagate(&mut self){for i in 1..=self.exponent{let base=(1<<(self.exponent-i))-1;for j in 0..(self.len>>i){let node=base+j;self.vec[node]=T::concat(i,self.vec[node*2+1],self.vec[node*2+2]);}}}fn eval(&mut self,node:usize,node_level:usize,node_left:usize,node_right:usize){if node_left>self.len{return;}let doubled_action=T::doubling_action(node_level,self.lazy[node]);let acted=T::action(node_level,doubled_action,self.vec[node]);if node_right-node_left>1{self.lazy[node*2+1]=T::action_mul(self.lazy[node],self.lazy[node*2+1]);self.lazy[node*2+2]=T::action_mul(self.lazy[node],self.lazy[node*2+2]);}if let Some(acted)=acted{self.vec[node]=acted;}else if node_right-node_left>1{let mid=(node_left+node_right)>>1;self.eval(node*2+1,node_level-1,node_left,mid);self.eval(node*2+2,node_level-1,mid,node_right);self.vec[node]=T::concat(node_level,self.vec[node*2+1],self.vec[node*2+2]);}else{panic!("Fail on one node...")}self.lazy[node]=T::ident_action();}fn sub_range_apply(&mut self,node:usize,node_level:usize,node_left:usize,node_right:usize,left:usize,right:usize,action:A,){self.eval(node,node_level,node_left,node_right);if node_right<=left||right<=node_left{}else if left<=node_left&&node_right<=right{self.lazy[node]=action;self.eval(node,node_level,node_left,node_right);}else{let mid=(node_left+node_right)>>1;self.sub_range_apply(node*2+1,node_level-1,node_left,mid,left,right,action,);self.sub_range_apply(node*2+2,node_level-1,mid,node_right,left,right,action,);self.vec[node]=T::concat(node_level-1,self.vec[node*2+1],self.vec[node*2+2],);}}pub fn range_apply(&mut self,left:usize,right:usize,action:A){self.sub_range_apply(0,self.exponent,0,1<<self.exponent,left,right,action);}fn sub_range_sum(&mut self,node:usize,node_level:usize,node_left:usize,node_right:usize,left:usize,right:usize,)->T{self.eval(node,node_level,node_left,node_right);if node_right<=left||right<=node_left{T::zero()}else if left<=node_left&&node_right<=right{self.vec[node]}else{let mid=(node_left+node_right)/2;let left_val=self.sub_range_sum(node*2+1,node_level-1,node_left,mid,left,right);let right_val=self.sub_range_sum(node*2+2,node_level-1,mid,node_right,left,right);T::concat(node_level-1,left_val,right_val)}}pub fn range_sum(&mut self,left:usize,right:usize)->T{self.sub_range_sum(0,self.exponent,0,1<<self.exponent,left,right)}}}pub mod interval_tree{use crate::__cargo_equip::preludes::minimal_lib_range::*;use std::collections::{HashMap,HashSet};use minimal_lib_int::utils::minimum_exponent;pub struct IntervalTree{ints:HashMap<usize,(usize,usize)>,v:Vec<HashSet<usize>>,n:usize,node_index:usize,exponent:usize,}impl IntervalTree{pub fn new(n:usize)->Self{let ex=minimum_exponent(n as i64);Self{ints:HashMap::new(),v:vec![HashSet::new();1<<(ex+1)],n,node_index:0,exponent:ex,}}fn sub_add(&mut self,node:usize,node_left:usize,node_right:usize,left:usize,right:usize,index:usize,){if node_right<=left||right<=node_left{}else if left<=node_left&&node_right<=right{self.v[node].insert(index);}else{let mid=(node_left+node_right)/2;self.sub_add(node*2+1,node_left,mid,left,right,index);self.sub_add(node*2+2,mid,node_right,left,right,index);}}fn sub_remove(&mut self,node:usize,node_left:usize,node_right:usize,left:usize,right:usize,index:usize,){if node_right<=left||right<=node_left{}else if left<=node_left&&node_right<=right{self.v[node].remove(&index);}else{let mid=(node_left+node_right)/2;self.sub_remove(node*2+1,node_left,mid,left,right,index);self.sub_remove(node*2+2,mid,node_right,left,right,index);}}pub fn add(&mut self,l:usize,r:usize)->usize{let ni=self.node_index;self.ints.insert(ni,(l,r));self.sub_add(0,0,1<<self.exponent,l,r,ni);self.node_index+=1;ni}pub fn remove(&mut self,ni:usize){let(l,r)=self.ints.remove(&ni).unwrap();self.sub_remove(0,0,1<<self.exponent,l,r,ni);}pub fn overlap(&self,x:usize)->Vec<(usize,usize,usize)>{let mut node=0;let mut node_left=0;let mut node_right=1<<self.exponent;let mut result=vec![];for i in self.v[node].iter(){let(l,r)=self.ints[i];result.push((*i,l,r));}for _i in 0..self.exponent{let mid=(node_left+node_right)/2;if x<mid{node_right=mid;node=node*2+1;for i in self.v[node].iter(){let(l,r)=self.ints[i];result.push((*i,l,r));}}else{node_left=mid;node=node*2+2;for i in self.v[node].iter(){let(l,r)=self.ints[i];result.push((*i,l,r));}}}result}}}pub mod traits{use crate::__cargo_equip::preludes::minimal_lib_range::*;use std::{cell::RefCell,marker::PhantomData,ops::Shl,ops::{Add,Deref},};use crate::__cargo_equip::crates::minimal_lib_range::lazysegtree::{LazyOpSegTree,LazySegOps};pub trait RangeQuery{type Item;fn range(&self,l:usize,r:usize)->Self::Item;fn put(&mut self,i:usize,v:Self::Item);fn get(&self,i:usize)->Self::Item;}pub trait RangeApplyQuery:RangeQuery{fn apply_range(&mut self,l:usize,r:usize,v:Self::Item);}struct OpAdd<T>where T:Add,{_dummy:PhantomData<fn()->T>,}impl<T>LazySegOps for OpAdd<T>where T:Add<T,Output=T>+Copy+Default+Shl<usize,Output=T>,{type Value=T;type Action=T;fn doubling_action(level:usize,action:Self::Action)->Self::Action{action<<level}fn concat(_level:usize,left:Self::Value,right:Self::Value)->Self::Value{left+right}fn action(_level:usize,action:Self::Action,value:Self::Value)->Self::Value{action+value}fn action_mul(lhs:Self::Action,rhs:Self::Action)->Self::Action{lhs+rhs}}pub struct RangeAddSegTree<T>where T:Add<T,Output=T>+Copy+Default+Shl<usize,Output=T>,{s:RefCell<LazyOpSegTree<T,T,OpAdd<T>>>,}impl<T>RangeAddSegTree<T>where T:Add<T,Output=T>+Copy+Default+Shl<usize,Output=T>,{fn new(n:usize)->Self{Self{s:RefCell::new(LazyOpSegTree::new(n)),}}}impl<T>From<Vec<T>>for RangeAddSegTree<T>where T:Add<T,Output=T>+Copy+Default+Shl<usize,Output=T>,{fn from(v:Vec<T>)->Self{let v=v.deref();let s=Self::new(v.len());{let mut seg=s.s.borrow_mut();for(i,x)in v.iter().enumerate(){seg.set_unpropagated(i,*x);}seg.propagate();}s}}impl<T>RangeQuery for RangeAddSegTree<T>where T:Add<T,Output=T>+Copy+Default+Shl<usize,Output=T>,{type Item=T;fn range(&self,l:usize,r:usize)->Self::Item{self.s.borrow_mut().range_sum(l,r)}fn put(&mut self,i:usize,v:Self::Item){self.s.borrow_mut().put(i,v)}fn get(&self,i:usize)->Self::Item{self.s.borrow_mut().range_sum(i,i+1)}}impl<T>RangeApplyQuery for RangeAddSegTree<T>where T:Add<T,Output=T>+Copy+Default+Shl<usize,Output=T>,{fn apply_range(&mut self,l:usize,r:usize,v:Self::Item){self.s.borrow_mut().range_apply(l,r,v)}}}}
    }

    pub(crate) mod macros {
        pub mod minimal_lib_algo {}
        pub mod minimal_lib_int {}
        pub mod minimal_lib_range {}
    }

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

    mod preludes {
        pub mod minimal_lib_algo {}
        pub mod minimal_lib_int {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::minimal_lib_algo;}
        pub mod minimal_lib_range {pub(in crate::__cargo_equip)use crate::__cargo_equip::crates::{minimal_lib_algo,minimal_lib_int};}
    }
}

Submission Info

Compile Error

warning: unused variable: `level`
  --> src/main.rs:16:24
   |
16 |     fn doubling_action(level: usize, action: Self::Action) -> Self::Action {
   |                        ^^^^^ help: if this is intentional, prefix it with an underscore: `_level`
   |
   = note: `#[warn(unused_variables)]` on by default

warning: unused variable: `level`
  --> src/main.rs:20:15
   |
20 |     fn concat(level: usize, left: Self::Value, right: Self::Value) -> Self::Value {
   |               ^^^^^ help: if this is intentional, prefix it with an underscore: `_level`

warning: unused variable: `level`
  --> src/main.rs:24:15
   |
24 |     fn action(level: usize, action: Self::Action, value: Self::Value) -> Self::Value {
   |               ^^^^^ help: if this is intentional, prefix it with an underscore: `_level`

Judge Result