// codesnip-guard: RangeFrequency
#[cfg_attr(any(),rustfmt::skip)]pub use self::range_frequency::RangeFrequency;#[cfg_attr(any(),rustfmt::skip)]mod range_frequency{use super::{AdditiveOperation,BinaryIndexedTree,FibHashMap};use std::{collections::hash_map::Entry,hash::Hash,mem::replace};#[derive(Debug,Clone,Copy)]enum RangeFrequencyQuery{Add{index:u32},Remove{index:u32},Query{left:u32,right:u32,output_index:u32}}#[derive(Debug,Clone)]pub struct RangeFrequency<T>where T:Clone+Eq+Hash{array:Vec<u32>,values:FibHashMap<T,u32>,events:Vec<(u32,RangeFrequencyQuery)>,queried:Vec<u8>,static_queries:Option<Vec<(u32,u32,u32,u32)>>,zero_queries:Vec<u32>,output_size:usize}impl<T>RangeFrequency<T>where T:Clone+Eq+Hash{pub fn new(array:Vec<T>)->Self{let mut result=Self{array:Vec::with_capacity(array.len()),values:FibHashMap::with_capacity_and_hasher(array.len(),Default::default()),events:Vec::new(),queried:Vec::new(),static_queries:Some(Vec::new()),zero_queries:Vec::new(),output_size:0};for value in array{let value=result.value_id(value);result.array.push(value);}result}fn value_id(&mut self,value:T)->u32{match self.values.entry(value){Entry::Occupied(entry)=>*entry.get(),Entry::Vacant(entry)=>{let id=self.queried.len()as u32;entry.insert(id);self.queried.push(0);id}}}pub fn set(&mut self,index:usize,value:T){if let Some(queries)=self.static_queries.take(){self.events.reserve(self.array.len()+queries.len()+2);for(index,&value)in self.array.iter().enumerate(){self.events.push((value,RangeFrequencyQuery::Add{index:index as u32}));}for(left,right,value,output_index)in queries{self.events.push((value,RangeFrequencyQuery::Query{left,right,output_index}));}}let value=self.value_id(value);let old_value=replace(&mut self.array[index],value);self.events.push((old_value,RangeFrequencyQuery::Remove{index:index as u32}));self.events.push((value,RangeFrequencyQuery::Add{index:index as u32}));}pub fn query(&mut self,left:usize,right:usize,value:T)->usize{let output_index=self.output_size;if let Some(&value)=self.values.get(&value){self.queried[value as usize]=1;if let Some(queries)=&mut self.static_queries{queries.push((left as u32,right as u32,value,output_index as u32));}else{self.events.push((value,RangeFrequencyQuery::Query{left:left as u32,right:right as u32,output_index:output_index as u32}));}}else{self.zero_queries.push(output_index as u32);}self.output_size+=1;output_index}pub fn execute_with_callback(mut self,mut callback:impl FnMut(usize,usize)){for output_index in self.zero_queries{callback(output_index as usize,0);}if let Some(mut queries)=self.static_queries.take(){let n=self.array.len();if queries.is_empty(){return;}let mut offsets=vec![0;n+2];for&(left,right,_,_)in&queries{if left<right{offsets[left as usize+1]+=1;offsets[right as usize+1]+=1;}}for i in 0..=n{offsets[i+1]+=offsets[i];}let mut next=offsets.clone();let mut events=vec![0u32;2*queries.len()];for(i,&(left,right,_,output_index))in queries.iter().enumerate(){if left>=right{callback(output_index as usize,0);continue;}for(side,position)in[left,right].into_iter().enumerate(){events[next[position as usize]]=(2*i+side)as u32;next[position as usize]+=1;}}let mut count=vec![0u32;self.values.len()];for position in 0..=n{for&endpoint in&events[offsets[position]..offsets[position+1]]{let query=(endpoint>>1)as usize;let frequency=count[queries[query].2 as usize];if endpoint&1==0{queries[query].0=frequency;}else{callback(queries[query].3 as usize,(frequency-queries[query].0)as usize);}}if position<n{count[self.array[position]as usize]+=1;}}return;}let mut processor=RangeFrequencyProcessor::new(self.array.len());for(index,value)in self.array.into_iter().enumerate(){self.events.push((value,RangeFrequencyQuery::Remove{index:index as u32}));}let mut offsets=vec![0;self.queried.len()+1];for&(value,_)in&self.events{offsets[value as usize+1]+=self.queried[value as usize]as usize;}for i in 0..self.queried.len(){offsets[i+1]+=offsets[i];}let mut next=offsets.clone();let mut events=vec![RangeFrequencyQuery::Add{index:0};*offsets.last().unwrap()];for(value,event)in self.events{let value=value as usize;if self.queried[value]!=0{events[next[value]]=event;next[value]+=1;}}for range in offsets.windows(2){for&query in&events[range[0]..range[1]]{match query{RangeFrequencyQuery::Add{index}=>{processor.add(index);}RangeFrequencyQuery::Remove{index}=>{processor.remove(index);}RangeFrequencyQuery::Query{left,right,output_index}=>{callback(output_index as usize,processor.query(left,right));}}}}}pub fn execute(self)->Vec<usize>{let mut results=vec![0;self.output_size];self.execute_with_callback(|i,v|results[i]=v);results}}#[derive(Debug,Clone)]struct RangeFrequencyProcessor{bit:BinaryIndexedTree<AdditiveOperation<i32>>,data:Vec<u64>}impl RangeFrequencyProcessor{fn new(size:usize)->Self{Self{bit:BinaryIndexedTree::new(size.div_ceil(64)),data:vec![0;size.div_ceil(64)]}}fn add(&mut self,index:u32){let index=index as usize;let(block,bit)=(index/64,index%64);assert!(self.data[block]&(1<<bit)==0);self.data[block]|=1<<bit;self.bit.update(block,1);}fn remove(&mut self,index:u32){let index=index as usize;let(i,j)=(index/64,index%64);assert!(self.data[i]&(1<<j)!=0);self.data[i]&=!(1<<j);self.bit.update(i,-1);}fn query(&self,left:u32,right:u32)->usize{if left>=right{return 0;}let(left,right)=(left as usize,right as usize-1);let(li,lj)=(left/64,left%64);let(ri,rj)=(right/64,right%64);let rj_r=63-rj;if li==ri{(self.data[li]<<rj_r>>(lj+rj_r)).count_ones()as usize}else{let mut ans=self.bit.fold(li+1,ri)as usize;ans+=(self.data[li]>>lj).count_ones()as usize;ans+=(self.data[ri]<<rj_r).count_ones()as usize;ans}}}}
// 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: FibonacciHash
#[cfg_attr(any(),rustfmt::skip)]pub use self::fibonacci_hash::{FibHashMap,FibHashSet,FibonacciHasher,FibonacciHasheru32,FibonacciHasheru64};#[cfg_attr(any(),rustfmt::skip)]mod fibonacci_hash{use std::{collections::{HashMap,HashSet},hash::{BuildHasherDefault,Hasher}};#[cfg(target_pointer_width="32")]pub type FibonacciHasher=FibonacciHasheru32;#[cfg(not(target_pointer_width="32"))]pub type FibonacciHasher=FibonacciHasheru64;pub type FibHashMap<K,V>=HashMap<K,V,BuildHasherDefault<FibonacciHasher>>;pub type FibHashSet<V>=HashSet<V,BuildHasherDefault<FibonacciHasher>>;#[derive(Debug,Default)]pub struct FibonacciHasheru32{hash:u32}impl FibonacciHasheru32{const A:u32=2654435769;const B:u32=5;fn push(&mut self,x:u32){self.hash=(self.hash.rotate_right(Self::B)^x).wrapping_mul(Self::A);}}impl Hasher for FibonacciHasheru32{fn finish(&self)->u64{self.hash as u64}fn write(&mut self,mut bytes:&[u8]){if bytes.len()%4>=2{let(chunk,rest)=bytes.split_first_chunk::<2>().unwrap();self.push(u16::from_ne_bytes(*chunk)as u32);bytes=rest;}if bytes.len()%2>=1{let(chunk,rest)=bytes.split_first_chunk::<1>().unwrap();self.push(u8::from_ne_bytes(*chunk)as u32);bytes=rest;}for chunk in bytes.as_chunks::<4>().0{self.push(u32::from_ne_bytes(*chunk));}}fn write_u8(&mut self,i:u8){self.push(i as u32)}fn write_u16(&mut self,i:u16){self.push(i as u32)}fn write_u32(&mut self,i:u32){self.push(i)}fn write_u64(&mut self,i:u64){self.push(i as u32);self.push((i>>32)as u32);}fn write_u128(&mut self,i:u128){self.push(i as u32);self.push((i>>32)as u32);self.push((i>>64)as u32);self.push((i>>96)as u32);}#[cfg(target_pointer_width="32")]fn write_usize(&mut self,i:usize){self.write_u32(i as u32)}#[cfg(target_pointer_width="64")]fn write_usize(&mut self,i:usize){self.write_u64(i as u64)}fn write_i8(&mut self,i:i8){self.write_u8(i as u8)}fn write_i16(&mut self,i:i16){self.write_u16(i as u16)}fn write_i32(&mut self,i:i32){self.write_u32(i as u32)}fn write_i64(&mut self,i:i64){self.write_u64(i as u64)}fn write_i128(&mut self,i:i128){self.write_u128(i as u128)}fn write_isize(&mut self,i:isize){self.write_usize(i as usize)}}#[derive(Debug,Default)]pub struct FibonacciHasheru64{hash:u64}impl FibonacciHasheru64{const A:u64=11400714819323198485;const B:u32=5;fn push(&mut self,x:u64){self.hash=(self.hash.rotate_right(Self::B)^x).wrapping_mul(Self::A);}}impl Hasher for FibonacciHasheru64{fn finish(&self)->u64{self.hash}fn write(&mut self,mut bytes:&[u8]){if bytes.len()%8>=4{let(chunk,rest)=bytes.split_first_chunk::<4>().unwrap();self.push(u32::from_ne_bytes(*chunk)as u64);bytes=rest;}if bytes.len()%4>=2{let(chunk,rest)=bytes.split_first_chunk::<2>().unwrap();self.push(u16::from_ne_bytes(*chunk)as u64);bytes=rest;}if bytes.len()%2>=1{let(chunk,rest)=bytes.split_first_chunk::<1>().unwrap();self.push(u8::from_ne_bytes(*chunk)as u64);bytes=rest;}for chunk in bytes.as_chunks::<8>().0{self.push(u64::from_ne_bytes(*chunk));}}fn write_u8(&mut self,i:u8){self.push(i as u64)}fn write_u16(&mut self,i:u16){self.push(i as u64)}fn write_u32(&mut self,i:u32){self.push(i as u64)}fn write_u64(&mut self,i:u64){self.push(i);}fn write_u128(&mut self,i:u128){self.push(i as u64);self.push((i>>64)as u64);}fn write_usize(&mut self,i:usize){self.write_u64(i as u64)}fn write_i8(&mut self,i:i8){self.write_u8(i as u8)}fn write_i16(&mut self,i:i16){self.write_u16(i as u16)}fn write_i32(&mut self,i:i32){self.write_u32(i as u32)}fn write_i64(&mut self,i:i64){self.write_u64(i as u64)}fn write_i128(&mut self,i:i128){self.write_u128(i as u128)}fn write_isize(&mut self,i:isize){self.write_usize(i as usize)}}}
// 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())});}