// codesnip-guard: RangeMinimumSubsetSize
#[cfg_attr(any(),rustfmt::skip)]pub use self::range_minimum_subset_size::RangeMinimumSubsetSize;#[cfg_attr(any(),rustfmt::skip)]mod range_minimum_subset_size{use super::{AdditiveOperation,BinaryIndexedTree};use std::ops::Range;#[derive(Debug,Clone)]pub struct RangeMinimumSubsetSize{values:Vec<i64>,events:Vec<RangeMinimumSubsetSizeEvent<i64>>,ranges:Vec<Range<usize>>,targets:Vec<i128>}impl RangeMinimumSubsetSize{pub fn new(values:impl IntoIterator<Item=i64>)->Self{let values:Vec<_>=values.into_iter().map(|x|x.max(0)).collect();let events=values.iter().enumerate().map(|(i,&x)|RangeMinimumSubsetSizeEvent::Update(i,x,1)).collect();Self{values,events,ranges:Vec::new(),targets:Vec::new()}}pub fn set(&mut self,index:usize,value:i64){let value=value.max(0);if self.values[index]!=value{self.events.push(RangeMinimumSubsetSizeEvent::Update(index,self.values[index],-1));self.events.push(RangeMinimumSubsetSizeEvent::Update(index,value,1));self.values[index]=value;}}#[doc=" Records a minimum subset size query for `sum >= target`; returns its result index."]pub fn query(&mut self,range:Range<usize>,target:i128)->usize{let id=self.ranges.len();self.ranges.push(range);self.targets.push(target);if target>0{self.events.push(RangeMinimumSubsetSizeEvent::Query(id));}id}#[doc=" Results in query order; `None` for unreachable targets."]pub fn execute(self)->Vec<Option<usize>>{let mut xs=vec![0];xs.extend(self.events.iter().filter_map(|e|match e{RangeMinimumSubsetSizeEvent::Update(_,x,_)=>Some(*x),RangeMinimumSubsetSizeEvent::Query(_)=>None,}));xs.sort_unstable();xs.dedup();let events:Vec<_>=self.events.into_iter().map(|e|match e{RangeMinimumSubsetSizeEvent::Update(p,x,delta)=>{RangeMinimumSubsetSizeEvent::Update(p,xs.binary_search(&x).unwrap(),delta)}RangeMinimumSubsetSizeEvent::Query(id)=>RangeMinimumSubsetSizeEvent::Query(id),}).collect();let mut eids:Vec<_>=(0..events.len()).collect();let mut buf=vec![0;eids.len()];let mut context=RangeMinimumSubsetSizeSolver{count:vec![0;self.ranges.len()],remaining:self.targets,ranges:self.ranges,bit:BinaryIndexedTree::new(self.values.len()),right:vec![false;events.len()],events,xs};context.dfs(0,context.xs.len(),&mut eids,&mut buf);context.count.into_iter().zip(context.remaining).map(|(count,remaining)|{if remaining>0{None}else{Some(count)}}).collect()}}#[derive(Debug,Clone,Copy)]enum RangeMinimumSubsetSizeEvent<T>{Update(usize,T,i64),Query(usize)}struct RangeMinimumSubsetSizeSolver{xs:Vec<i64>,events:Vec<RangeMinimumSubsetSizeEvent<usize>>,ranges:Vec<Range<usize>>,remaining:Vec<i128>,count:Vec<usize>,bit:BinaryIndexedTree<(AdditiveOperation<i64>,AdditiveOperation<i128>)>,right:Vec<bool>}impl RangeMinimumSubsetSizeSolver{fn dfs(&mut self,lo:usize,hi:usize,eids:&mut[usize],buf:&mut[usize]){if eids.is_empty(){return;}if lo+1==hi{if self.xs[lo]>0{let x=i128::from(self.xs[lo]);for&eid in eids.iter(){if let RangeMinimumSubsetSizeEvent::Query(id)=self.events[eid]{let remaining=self.remaining[id];self.count[id]+=((remaining-1)/x+1)as usize;self.remaining[id]=0;}}}return;}let mid=(lo+hi)/2;let mut nl=0;for&eid in eids.iter(){match self.events[eid]{RangeMinimumSubsetSizeEvent::Update(p,v,delta)=>{self.right[eid]=v>=mid;if self.right[eid]{self.bit.update(p,(delta,i128::from(delta)*i128::from(self.xs[v])));}else{nl+=1;}}RangeMinimumSubsetSizeEvent::Query(id)=>{let range=&self.ranges[id];let(count,sum)=self.bit.fold(range.start,range.end);self.right[eid]=sum>=self.remaining[id];if!self.right[eid]{self.remaining[id]-=sum;self.count[id]+=count as usize;nl+=1;}}}}let(mut il,mut ir)=(0,nl);for&eid in eids.iter(){if let RangeMinimumSubsetSizeEvent::Update(p,v,delta)=self.events[eid]&&self.right[eid]{self.bit.update(p,(-delta,-i128::from(delta)*i128::from(self.xs[v])));}if self.right[eid]{buf[ir]=eid;ir+=1;}else{buf[il]=eid;il+=1;}}let(el,er)=buf.split_at_mut(nl);let(bl,br)=eids.split_at_mut(nl);self.dfs(lo,mid,el,bl);self.dfs(mid,hi,er,br);}}}
// codesnip-guard: AdditiveOperation
#[cfg_attr(any(),rustfmt::skip)]pub use self::additive_operation_impl::AdditiveOperation;#[cfg_attr(any(),rustfmt::skip)]mod additive_operation_impl{use super::*;use std::{marker::PhantomData,ops::{Add,Neg,Sub}};#[doc=" $+$"]pub struct AdditiveOperation<T>where T:Clone+Zero+Add<Output=T>{_marker:PhantomData<fn()->T>}impl<T>Magma for AdditiveOperation<T>where T:Clone+Zero+Add<Output=T>{type T=T;#[inline]fn operate(x:&Self::T,y:&Self::T)->Self::T{x.clone()+y.clone()}}impl<T>Unital for AdditiveOperation<T>where T:Clone+Zero+Add<Output=T>{#[inline]fn unit()->Self::T{Zero::zero()}}impl<T>Associative for AdditiveOperation<T>where T:Clone+Zero+Add<Output=T>{}impl<T>Commutative for AdditiveOperation<T>where T:Clone+Zero+Add<Output=T>{}impl<T>Invertible for AdditiveOperation<T>where T:Clone+Zero+Add<Output=T>+Sub<Output=T>+Neg<Output=T>{#[inline]fn inverse(x:&Self::T)->Self::T{-x.clone()}#[inline]fn rinv_operate(x:&Self::T,y:&Self::T)->Self::T{x.clone()-y.clone()}}}
// codesnip-guard: BinaryIndexedTree
#[cfg_attr(any(),rustfmt::skip)]pub use self::binary_indexed_tree::BinaryIndexedTree;#[cfg_attr(any(),rustfmt::skip)]mod binary_indexed_tree{use super::{AbelianGroup,Group,Monoid};use std::fmt::{self,Debug,Formatter};pub struct BinaryIndexedTree<M>where M:Monoid{n:usize,bit:Vec<M::T>}impl<M>Clone for BinaryIndexedTree<M>where M:Monoid{fn clone(&self)->Self{Self{n:self.n,bit:self.bit.clone()}}}impl<M>Debug for BinaryIndexedTree<M>where M:Monoid<T:Debug>{fn fmt(&self,f:&mut Formatter<'_>)->fmt::Result{f.debug_struct("BinaryIndexedTree").field("n",&self.n).field("bit",&self.bit).finish()}}impl<M>BinaryIndexedTree<M>where M:Monoid{#[inline]pub fn new(n:usize)->Self{let bit=vec![M::unit();n+1];Self{n,bit}}#[inline]pub fn from_slice(slice:&[M::T])->Self{let n=slice.len();let mut bit=vec![M::unit();n+1];for(i,x)in slice.iter().enumerate(){let k=i+1;M::operate_assign(&mut bit[k],x);let j=k+(k&(!k+1));if j<=n{bit[j]=M::operate(&bit[j],&bit[k]);}}Self{n,bit}}#[inline]#[doc=" fold [0, k)"]pub fn accumulate0(&self,mut k:usize)->M::T{debug_assert!(k<=self.n);let mut res=M::unit();while k>0{res=M::operate(&self.bit[k],&res);k-=k&(!k+1);}res}#[inline]#[doc=" fold [0, k]"]pub fn accumulate(&self,k:usize)->M::T{self.accumulate0(k+1)}#[inline]pub fn update(&mut self,k:usize,x:M::T){debug_assert!(k<self.n);let mut k=k+1;while k<=self.n{self.bit[k]=M::operate(&self.bit[k],&x);k+=k&(!k+1);}}#[inline]pub fn partition_point_acc<P>(&self,mut pred:P)->usize where P:FnMut(&M::T)->bool{let n=self.n;let mut acc=M::unit();let mut pos=0;let mut k=n.next_power_of_two();while k>0{if k+pos<=n{let nacc=M::operate(&acc,&self.bit[k+pos]);if pred(&nacc){pos+=k;acc=nacc;}}k>>=1;}pos}}impl<G:Group>BinaryIndexedTree<G>{#[inline]pub fn fold(&self,l:usize,r:usize)->G::T{debug_assert!(l<=self.n&&r<=self.n);G::operate(&G::inverse(&self.accumulate0(l)),&self.accumulate0(r))}#[inline]pub fn fold_abelian(&self,mut l:usize,mut r:usize)->G::T where G:AbelianGroup{debug_assert!(l<=self.n&&r<=self.n);if l==r{return G::unit();}let common=l&!(usize::MAX>>(l^r).leading_zeros());let mut left=G::unit();let mut right=G::unit();while l!=common{G::operate_assign(&mut left,&self.bit[l]);l&=l-1;}while r!=common{G::operate_assign(&mut right,&self.bit[r]);r&=r-1;}G::rinv_operate(&right,&left)}#[inline]pub fn get(&self,k:usize)->G::T{self.fold(k,k+1)}#[inline]pub fn set(&mut self,k:usize,x:G::T){self.update(k,G::operate(&G::inverse(&self.get(k)),&x));}}}
// codesnip-guard: TupleOperation
#[cfg_attr(any(),rustfmt::skip)]mod tuple_operation_impl{use super::*;macro_rules!impl_tuple_operation{(@impl)=>{impl Magma for(){type T=();fn operate(_x:&Self::T,_y:&Self::T)->Self::T{}}impl Unital for(){fn unit()->Self::T{}}impl Associative for(){}impl Commutative for(){}impl Idempotent for(){}impl Invertible for(){fn inverse(_x:&Self::T)->Self::T{}}};(@impl$($T:ident$i:tt)*)=>{impl<$($T:Magma),*>Magma for($($T,)*){type T=($(<$T as Magma>::T,)*);fn operate(x:&Self::T,y:&Self::T)->Self::T{($(<$T as Magma>::operate(&x.$i,&y.$i),)*)}}impl<$($T:Unital),*>Unital for($($T,)*){fn unit()->Self::T{($(<$T as Unital>::unit(),)*)}}impl<$($T:Associative),*>Associative for($($T,)*){}impl<$($T:Commutative),*>Commutative for($($T,)*){}impl<$($T:Idempotent),*>Idempotent for($($T,)*){}impl<$($T:Invertible),*>Invertible for($($T,)*){fn inverse(x:&Self::T)->Self::T{($(<$T as Invertible>::inverse(&x.$i),)*)}}};(@inner$($T:ident$i:tt)*;$U:ident$j:tt$($t:tt)*)=>{impl_tuple_operation!(@impl$($T$i)*);impl_tuple_operation!(@inner$($T$i)*$U$j;$($t)*);};(@inner$($T:ident$i:tt)*;)=>{impl_tuple_operation!(@impl$($T$i)*);};($($t:tt)*)=>{impl_tuple_operation!(@inner;$($t)*);};}impl_tuple_operation!(A 0 B 1 C 2 D 3 E 4 F 5 G 6 H 7 I 8 J 9);}
// codesnip-guard: algebra
#[cfg_attr(any(),rustfmt::skip)]pub use self::magma::*;#[cfg_attr(any(),rustfmt::skip)]mod magma{#![doc=" algebraic traits"]#[doc=" binary operaion: $T \\circ T \\to T$"]pub trait Magma{#[doc=" type of operands: $T$"]type T:Clone;#[doc=" binary operaion: $\\circ$"]fn operate(x:&Self::T,y:&Self::T)->Self::T;fn reverse_operate(x:&Self::T,y:&Self::T)->Self::T{Self::operate(y,x)}fn operate_assign(x:&mut Self::T,y:&Self::T){*x=Self::operate(x,y);}}#[doc=" $\\forall a,\\forall b,\\forall c \\in T, (a \\circ b) \\circ c = a \\circ (b \\circ c)$"]pub trait Associative:Magma{}#[doc=" associative binary operation"]pub trait SemiGroup:Magma+Associative{}impl<S>SemiGroup for S where S:Magma+Associative{}#[doc=" $\\exists e \\in T, \\forall a \\in T, e \\circ a = a \\circ e = a$"]pub trait Unital:Magma{#[doc=" identity element: $e$"]fn unit()->Self::T;fn is_unit(x:&Self::T)->bool where Self::T:PartialEq{x==&Self::unit()}fn set_unit(x:&mut Self::T){*x=Self::unit();}}pub trait ExpBits{type Iter:Iterator<Item=bool>;fn bits(self)->Self::Iter;}pub trait SignedExpBits{type T:ExpBits;fn neg_and_bits(self)->(bool,Self::T);}pub struct Bits<T>{n:T}macro_rules!impl_exp_bits_for_uint{($($t:ty)*)=>{$(impl Iterator for Bits<$t>{type Item=bool;fn next(&mut self)->Option<bool>{if self.n==0{None}else{let bit=(self.n&1)==1;self.n>>=1;Some(bit)}}}impl ExpBits for$t{type Iter=Bits<$t>;fn bits(self)->Self::Iter{Bits{n:self}}}impl SignedExpBits for$t{type T=$t;fn neg_and_bits(self)->(bool,Self::T){(false,self)}})*};}impl_exp_bits_for_uint!(u8 u16 u32 u64 u128 usize);macro_rules!impl_signed_exp_bits_for_sint{($($s:ty,$u:ty;)*)=>{$(impl SignedExpBits for$s{type T=$u;fn neg_and_bits(self)->(bool,Self::T){(self<0,self.unsigned_abs())}})*};}impl_signed_exp_bits_for_sint!(i8,u8;i16,u16;i32,u32;i64,u64;i128,u128;isize,usize;);#[doc=" associative binary operation and an identity element"]pub trait Monoid:SemiGroup+Unital{#[doc=" binary exponentiation: $x^n = x\\circ\\ddots\\circ x$"]fn pow<E>(mut x:Self::T,exp:E)->Self::T where E:ExpBits{let mut bits=exp.bits();let Some(first)=bits.next()else{return Self::unit();};let mut res=if first{x.clone()}else{Self::unit()};for bit in bits{x=Self::operate(&x,&x);if bit{res=Self::operate(&res,&x);}}res}fn fold<I>(iter:I)->Self::T where I:IntoIterator<Item=Self::T>{let mut iter=iter.into_iter();if let Some(item)=iter.next(){iter.fold(item,|acc,x|Self::operate(&acc,&x))}else{Self::unit()}}}impl<M>Monoid for M where M:SemiGroup+Unital{}#[doc=" $\\exists e \\in T, \\forall a \\in T, \\exists b,c \\in T, b \\circ a = a \\circ c = e$"]pub trait Invertible:Magma+Unital{#[doc=" $a$ where $a \\circ x = e$"]fn inverse(x:&Self::T)->Self::T;fn rinv_operate(x:&Self::T,y:&Self::T)->Self::T{Self::operate(x,&Self::inverse(y))}fn rinv_operate_assign(x:&mut Self::T,y:&Self::T){*x=Self::rinv_operate(x,y);}}#[doc=" associative binary operation and an identity element and inverse elements"]pub trait Group:Monoid+Invertible{fn signed_pow<E>(x:Self::T,exp:E)->Self::T where E:SignedExpBits{let(neg,exp)=E::neg_and_bits(exp);let res=Self::pow(x,exp);if neg{Self::inverse(&res)}else{res}}}impl<G>Group for G where G:Monoid+Invertible{}#[doc=" $\\forall a,\\forall b \\in T, a \\circ b = b \\circ a$"]pub trait Commutative:Magma{}#[doc=" commutative monoid"]pub trait AbelianMonoid:Monoid+Commutative{}impl<M>AbelianMonoid for M where M:Monoid+Commutative{}#[doc=" commutative group"]pub trait AbelianGroup:Group+Commutative{}impl<G>AbelianGroup for G where G:Group+Commutative{}#[doc=" $\\forall a \\in T, a \\circ a = a$"]pub trait Idempotent:Magma{}#[doc=" idempotent monoid"]pub trait IdempotentMonoid:Monoid+Idempotent{}impl<M>IdempotentMonoid for M where M:Monoid+Idempotent{}#[macro_export]macro_rules!monoid_fold{($m:ty)=>{<$m as Unital>::unit()};($m:ty,)=>{<$m as Unital>::unit()};($m:ty,$f:expr)=>{$f};($m:ty,$f:expr,$($ff:expr),*)=>{<$m as Magma>::operate(&($f),&monoid_fold!($m,$($ff),*))};}#[macro_export]macro_rules!define_monoid{($Name:ident,$t:ty,|$x:ident,$y:ident|$op:expr,$unit:expr)=>{struct$Name;impl Magma for$Name{type T=$t;fn operate($x:&Self::T,$y:&Self::T)->Self::T{$op}}impl Unital for$Name{fn unit()->Self::T{$unit}}impl Associative for$Name{}};}}
// codesnip-guard: zero_one
#[cfg_attr(any(),rustfmt::skip)]pub use self::zero_one::{One,Zero};#[cfg_attr(any(),rustfmt::skip)]mod zero_one{pub trait Zero:Sized{fn zero()->Self;#[inline]fn is_zero(&self)->bool where Self:PartialEq{self==&Self::zero()}#[inline]fn set_zero(&mut self){*self=Self::zero();}}pub trait One:Sized{fn one()->Self;#[inline]fn is_one(&self)->bool where Self:PartialEq{self==&Self::one()}#[inline]fn set_one(&mut self){*self=Self::one();}}macro_rules!impl_zero_one{($({$(<$T:ident:$Bound:ident>)?$Trait:ident$method:ident$($t:ty)*,$e:expr})*)=>{$(impl_zero_one!(@impl[$(<$T:$Bound>)?]$Trait$method[$($t)*],$e);)*};(@impl[<$T:ident:$Bound:ident>]$Trait:ident$method:ident[$($t:ty)*],$e:expr)=>{$(impl<$T:$Bound>$Trait for$t{fn$method()->Self{$e}})*};(@impl[]$Trait:ident$method:ident[$($t:ty)*],$e:expr)=>{$(impl$Trait for$t{fn$method()->Self{$e}})*};}impl_zero_one!({Zero zero u8 u16 u32 u64 usize i8 i16 i32 i64 isize u128 i128,0}{Zero zero f32 f64,0.}{One one u8 u16 u32 u64 usize i8 i16 i32 i64 isize u128 i128,1}{One one f32 f64,1.}{<T:Zero>Zero zero std::num::Wrapping<T>,Self(T::zero())}{<T:One>One one std::num::Wrapping<T>,Self(T::one())});}