#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize(2)
#include<cstdio>
#include<cmath>
#define LL long long
#define Re register int
#define F(x,a,b) for(Re x=a;x<=b;++x)
const int N=5e4+3,T=230;
int n,t,x,l,r,Q,fu,pt[N],L[T],R[T];LL a[N],S[T],add[T];
inline void in(Re &x){
x=fu=0;char c=getchar();
while(c<'0'||c>'9')fu|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=fu?-x:x;
}
inline void change(Re l,Re r,Re x){
Re p=pt[l],q=pt[r];
if(p==q){F(i,l,r)a[i]+=x;S[p]+=x*(r-l+1);}
else{
F(i,p+1,q-1)add[i]+=x;
F(i,l,R[p])a[i]+=x;S[p]+=x*(R[p]-l+1);
F(i,L[q],r)a[i]+=x;S[q]+=x*(r-L[q]+1);
}
}
inline LL ask(Re x){return a[x]+add[pt[x]];}
int main(){
in(n),t=sqrt(Q=n);
F(i,1,t)L[i]=(i-1)*t+1,R[i]=i*t;
if(R[t]<n)R[++t]=n,L[t]=R[t-1]+1;
F(i,1,n)in(x),a[i]=x;
F(i,1,t)F(j,L[i],R[i])pt[j]=i,S[i]+=a[j];
while(Q--){
in(n),in(l),in(r),in(x);
if(n)printf("%lld\n",ask(r));
else change(l,r,x);
}
}
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize(2)
#include<algorithm>
#include<cstdio>
#include<cmath>
#define LL long long
#define Re register int
#define F(x,a,b) for(Re x=a;x<=b;++x)
#define lo(l,r,x) (lower_bound(b+l,b+r+1,x)-b)
using namespace std;
const int N=5e4+3,T=230;
int n,t,x,l,r,o,Q,fu,pt[N],L[T],R[T];LL a[N],b[N],add[T];
inline void in(Re &x){
x=fu=0;char c=getchar();
while(c<'0'||c>'9')fu|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=fu?-x:x;
}
inline void sak(Re l,Re r,Re p,Re x){F(i,l,r)a[i]+=x;F(i,L[p],R[p])b[i]=a[i];sort(b+L[p],b+R[p]+1);}
inline void change(Re l,Re r,Re x){
Re p=pt[l],q=pt[r];
if(p==q)sak(l,r,p,x);
else{
F(i,p+1,q-1)add[i]+=x;
sak(l,R[p],p,x),sak(L[q],r,q,x);
}
}
inline LL ask(Re l,Re r,LL x){
Re p=pt[l],q=pt[r];LL ans=0;
if(p==q){F(i,l,r)ans+=a[i]+add[p]<x;return ans;}
else{
F(i,p+1,q-1)ans+=lo(L[i],R[i],x-add[i])-L[i];
F(i,l,R[p])ans+=a[i]+add[p]<x;
F(i,L[q],r)ans+=a[i]+add[q]<x;
}
return ans;
}
int main(){
in(n),t=sqrt(Q=n);
F(i,1,t)L[i]=(i-1)*t+1,R[i]=i*t;
if(R[t]<n)R[++t]=n,L[t]=R[t-1]+1;
F(i,1,n)in(x),a[i]=b[i]=x;
F(i,1,t)F(j,L[i],R[i])pt[j]=i;
F(i,1,t)sort(b+L[i],b+R[i]+1);
while(Q--){
in(o),in(l),in(r),in(x);
if(o)printf("%lld\n",ask(l,r,(LL)x*x));
else change(l,r,x);
}
}
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize(2)
#include<algorithm>
#include<cstdio>
#include<cmath>
#define inf -2147483647
#define Re register int
#define F(x,a,b) for(Re x=a;x<=b;++x)
using namespace std;
const int N=1e5+3,T=330;
int n,t,x,l,r,o,Q,fu,pt[N],L[T],R[T],a[N],b[N],add[T];
inline void in(Re &x){
x=fu=0;char c=getchar();
while(c<'0'||c>'9')fu|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=fu?-x:x;
}
inline void sak(Re l,Re r,Re p,Re x){F(i,l,r)a[i]+=x;F(i,L[p],R[p])b[i]=a[i];sort(b+L[p],b+R[p]+1);}
inline void change(Re l,Re r,Re x){
Re p=pt[l],q=pt[r];
if(p==q)sak(l,r,p,x);
else{
F(i,p+1,q-1)add[i]+=x;
sak(l,R[p],p,x),sak(L[q],r,q,x);
}
}
inline int ask(Re l,Re r,Re x){
Re p=pt[l],q=pt[r],ans=inf,w;
if(p==q){F(i,l,r)if(a[i]+add[p]<x)ans=max(ans,a[i]+add[p]);}
else{
F(i,p+1,q-1)w=lower_bound(b+L[i],b+R[i]+1,x-add[i])-(b+1),ans=w>=L[i]?max(ans,b[w]+add[i]):ans;
F(i,l,R[p])if(a[i]+add[p]<x)ans=max(ans,a[i]+add[p]);
F(i,L[q],r)if(a[i]+add[q]<x)ans=max(ans,a[i]+add[q]);
}
return ans==inf?-1:ans;
}
int main(){
in(n),t=sqrt(Q=n);
F(i,1,t)L[i]=(i-1)*t+1,R[i]=i*t;
if(R[t]<n)R[++t]=n,L[t]=R[t-1]+1;
F(i,1,n)in(x),a[i]=b[i]=x;
F(i,1,t)F(j,L[i],R[i])pt[j]=i;
F(i,1,t)sort(b+L[i],b+R[i]+1);
while(Q--){
in(o),in(l),in(r),in(x);
if(o)printf("%d\n",ask(l,r,x));
else change(l,r,x);
}
}
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize(2)
#include<cstdio>
#include<cmath>
#define LL long long
#define Re register int
#define F(x,a,b) for(Re x=a;x<=b;++x)
const int N=5e4+3,T=230;
int n,t,x,l,r,Q,fu,pt[N],L[T],R[T];LL a[N],S[T],add[T];
inline void in(Re &x){
x=fu=0;char c=getchar();
while(c<'0'||c>'9')fu|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=fu?-x:x;
}
inline void change(Re l,Re r,Re x){
Re p=pt[l],q=pt[r];
if(p==q){F(i,l,r)a[i]+=x;S[p]+=(LL)x*(r-l+1);}
else{
F(i,p+1,q-1)add[i]+=x;
F(i,l,R[p])a[i]+=x;S[p]+=(LL)x*(R[p]-l+1);
F(i,L[q],r)a[i]+=x;S[q]+=(LL)x*(r-L[q]+1);
}
}
inline LL ask(Re l,Re r){
Re p=pt[l],q=pt[r];LL ans=0;
if(p==q){F(i,l,r)ans+=a[i];ans+=add[p]*(r-l+1);}
else{
F(i,p+1,q-1)ans+=S[i]+add[i]*(LL)(R[i]-L[i]+1);
F(i,l,R[p])ans+=a[i];ans+=add[p]*(LL)(R[p]-l+1);
F(i,L[q],r)ans+=a[i];ans+=add[q]*(LL)(r-L[q]+1);
}
return ans;
}
int main(){
in(n),t=sqrt(Q=n);
F(i,1,t)L[i]=(i-1)*t+1,R[i]=i*t;
if(R[t]<n)R[++t]=n,L[t]=R[t-1]+1;
F(i,1,n)in(x),a[i]=x;
F(i,1,t)F(j,L[i],R[i])pt[j]=i,S[i]+=a[j];
while(Q--){
in(n),in(l),in(r),in(x);
if(n)printf("%lld\n",ask(l,r)%(x+1));
else change(l,r,x);
}
}
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize(2)
#include<cstdio>
#include<cmath>
#define LL long long
#define Re register int
#define F(x,a,b) for(Re x=a;x<=b;++x)
const int N=5e4+3,T=230;
int n,t,x,l,r,Q,fu,pt[N],L[T],R[T],pan[T];LL a[N],S[T];
inline void in(Re &x){
x=fu=0;char c=getchar();
while(c<'0'||c>'9')fu|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=fu?-x:x;
}
inline void sakura(Re p){
if(pan[p])return;pan[p]=1,S[p]=0;
F(i,L[p],R[p])S[p]+=(a[i]=sqrt(a[i])),pan[p]&=(a[i]<=1);
}
inline void change(Re l,Re r){
Re p=pt[l],q=pt[r];
if(p==q){F(i,l,r)S[p]-=a[i],a[i]=sqrt(a[i]),S[p]+=a[i];}
else{
F(i,p+1,q-1)sakura(i);
F(i,l,R[p])S[p]-=a[i],a[i]=sqrt(a[i]),S[p]+=a[i];
F(i,L[q],r)S[q]-=a[i],a[i]=sqrt(a[i]),S[q]+=a[i];
}
}
inline LL ask(Re l,Re r){
Re p=pt[l],q=pt[r];LL ans=0;
if(p==q){F(i,l,r)ans+=a[i];}
else{
F(i,p+1,q-1)ans+=S[i];
F(i,l,R[p])ans+=a[i];
F(i,L[q],r)ans+=a[i];
}
return ans;
}
int main(){
in(n),t=sqrt(Q=n);
F(i,1,t)L[i]=(i-1)*t+1,R[i]=i*t;
if(R[t]<n)R[++t]=n,L[t]=R[t-1]+1;
F(i,1,n)in(x),a[i]=x;
F(i,1,t)F(j,L[i],R[i])pt[j]=i,S[i]+=a[j];
while(Q--){
in(n),in(l),in(r),in(x);
if(n)printf("%lld\n",ask(l,r));
else change(l,r);
}
}
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize(2)
#include<vector>
#include<cstdio>
#include<cmath>
#define Re register int
#define F(x,a,b) for(Re x=a;x<=b;++x)
using namespace std;
const int N=1e5+3,T=330;
int n,o,t,x,l,r,Q,fu,pt[N],pw[N],L[T],R[T];
vector<int>a[T];
inline void in(Re &x){
x=fu=0;char c=getchar();
while(c<'0'||c>'9')fu|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=fu?-x:x;
}
inline void change(Re w,Re x){
F(i,1,t)
if(w>a[i].size())w-=a[i].size();
else{a[i].insert(a[i].begin()+w-1,x);return;}
}
inline int ask(Re w){
F(i,1,t)
if(w>a[i].size())w-=a[i].size();
else return a[i][w-1];
}
int main(){
in(n),t=sqrt(Q=n);
F(i,1,t)L[i]=(i-1)*t+1,R[i]=i*t;
if(R[t]<n)R[++t]=n,L[t]=R[t-1]+1;
F(i,1,t){F(j,L[i],R[i])in(x),a[i].push_back(x),pt[j]=i;}
while(Q--){
in(o),in(l),in(r),in(x);
if(o)printf("%d\n",ask(r));
else change(l,r);
}
}
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize(2)
#include<cstdio>
#include<cmath>
#define Re register int
#define F(x,a,b) for(Re x=a;x<=b;++x)
const int N=1e5+3,T=320;
int n,t,x,l,r,Q,fu,P=10007,pt[N],L[T],R[T],a[N],add[T],mul[T];
inline void in(Re &x){
x=fu=0;char c=getchar();
while(c<'0'||c>'9')fu|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=fu?-x:x;
}
inline void spread(Re p){
F(i,L[p],R[p])(((a[i]*=mul[p])%=P)+=add[p])%=P;
add[p]=0,mul[p]=1;
}
inline void change(Re l,Re r,Re x){
Re p=pt[l],q=pt[r];spread(p);
if(p==q)F(i,l,r)(a[i]+=x)%=P;
else{
spread(q);
F(i,p+1,q-1)(add[i]+=x)%P;
F(i,l,R[p])(a[i]+=x)%=P;
F(i,L[q],r)(a[i]+=x)%=P;
}
}
inline void change2(Re l,Re r,Re x){
Re p=pt[l],q=pt[r];spread(p);
if(p==q)F(i,l,r)(a[i]*=x)%=P;
else{
spread(q);
F(i,p+1,q-1)(add[i]*=x)%=P,(mul[i]*=x)%=P;
F(i,l,R[p])(a[i]*=x)%=P;
F(i,L[q],r)(a[i]*=x)%=P;
}
}
inline int ask(Re x){return (a[x]*mul[pt[x]]%P+add[pt[x]])%P;}
int main(){
in(n),t=sqrt(Q=n);
F(i,1,t)L[i]=(i-1)*t+1,R[i]=i*t,mul[i]=1;
if(R[t]<n)R[++t]=n,L[t]=R[t-1]+1,mul[t]=1;
F(i,1,n)in(a[i]);
F(i,1,t)F(j,L[i],R[i])pt[j]=i;
while(Q--){
in(n),in(l),in(r),in(x);
if(n>1)printf("%d\n",ask(r));
else n?change2(l,r,x%P):change(l,r,x%P);
}
}
#pragma GCC diagnostic error "-std=c++11"
#pragma GCC target("avx")
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include<cstdio>
#include<cmath>
#define Re register int
#define F(x,a,b) for(Re x=a;x<=b;++x)
const int N=1e5+3,T=330;
int n,t,x,l,r,Q,fu,pt[N],L[T],R[T],a[N],tag[T];
inline void in(Re &x){
x=fu=0;char c=getchar();
while(c<'0'||c>'9')fu|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=fu?-x:x;
}
inline int sak(Re l,Re r,Re p,Re x){
Re tmp=0;
if(tag[p]!=-1){F(i,L[p],R[p])a[i]=tag[p];tmp+=(r-l+1)*(tag[p]==x);}
else F(i,l,r)tmp+=a[i]==x;
tag[p]=-1;F(i,l,r)a[i]=x;
return tmp;
}
inline int fuck(Re p,Re x){
Re tmp=0;
if(tag[p]!=-1){F(j,L[p],R[p])a[j]=tag[p];tmp+=(R[p]-L[p]+1)*(tag[p]==x);}
else F(j,L[p],R[p])tmp+=a[j]==x;
tag[p]=x;
return tmp;
}
inline int sovle(Re l,Re r,Re x){
Re p=pt[l],q=pt[r],ans=0;
if(p==q)return l==r?fuck(p,x):sak(l,r,p,x);
else{
F(i,p+1,q-1)ans+=fuck(i,x);
ans+=sak(l,R[p],p,x)+sak(L[q],r,q,x);
}
return ans;
}
int main(){
in(n),t=sqrt(Q=n);
F(i,1,t)L[i]=(i-1)*t+1,R[i]=i*t;
if(R[t]<n)R[++t]=n,L[t]=R[t-1]+1;
F(i,1,n)in(x),a[i]=x;
F(i,1,t){tag[i]=-1;F(j,L[i],R[i])pt[j]=i;}
while(Q--){
in(l),in(r),in(x);
printf("%d\n",sovle(l,r,x));
}
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LL long long
#define Re register int
using namespace std;
const int N=1e5+3,M=1e5+3;
int n,m,T,BL,BLN,A[N],b[N],Li[325],Ri[325],cnt[N],cnt_[N],belong[N];LL Ans[M];
struct Query{
int l,r,id;
inline bool operator<(const Query &O)const{
Re B1=belong[l],B2=belong[O.l];
return B1!=B2?B1<B2:r<O.r;
}
}Q[M];
inline void in(Re &x){
Re fu=0;x=0;char c=getchar();
while(c<'0'||c>'9')fu|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=fu?-x:x;
}
int main(){
// freopen("123.txt","r",stdin);
in(n),in(T),BL=sqrt(n)+1,BLN=n/BL+1;
for(Re i=1;i<=BLN;++i){
Li[i]=(i-1)*BL+1,Ri[i]=min(i*BL,n);
for(Re j=Li[i];j<=Ri[i];++j)belong[j]=i;
}
for(Re i=1;i<=n;++i)in(A[i]),b[i]=A[i];
sort(b+1,b+n+1),m=unique(b+1,b+n+1)-b-1;
for(Re i=1;i<=n;++i)A[i]=lower_bound(b+1,b+m+1,A[i])-b;
for(Re i=1;i<=T;++i)in(Q[i].l),in(Q[i].r),Q[i].id=i;
sort(Q+1,Q+T+1);Re i=1;
for(Re p=1;p<=BLN;++p){
Re nowL=Ri[p]+1,nowR=Ri[p];LL ans=0;
memset(cnt,0,sizeof(cnt));
while(belong[Q[i].l]==p){
Re L=Q[i].l,R=Q[i].r;
if(belong[L]==belong[R]){
LL tmp=0;
for(Re j=L;j<=R;++j)cnt_[A[j]]=0;
for(Re j=L;j<=R;++j)++cnt_[A[j]],tmp=max(tmp,(LL)b[A[j]]*cnt_[A[j]]);
Ans[Q[i].id]=tmp;
}
else{
while(nowR<R)cnt[A[++nowR]]++,ans=max(ans,(LL)b[A[nowR]]*cnt[A[nowR]]);
LL tmp=ans;
while(nowL>L)cnt[A[--nowL]]++,tmp=max(tmp,(LL)b[A[nowL]]*cnt[A[nowL]]);
Ans[Q[i].id]=tmp;
while(nowL<Ri[p]+1)--cnt[A[nowL++]];
}
++i;
}
}
for(Re i=1;i<=T;++i)printf("%lld\n",Ans[i]);
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#define Re register int
using namespace std;
const int N=2e5+3,M=2e5+3,INF=1e6+3;
int n,x,y,T,TQ,TC,BL,ans,a[N],Ans[M],cnt[INF];char op;
struct Query{
int l,r,id,time;
inline bool operator<(const Query &O)const{
Re B1=l/BL,B2=O.l/BL,B3=r/BL,B4=O.r/BL;
return B1!=B2?B1<B2:(B3!=B4?B3<B4:time<O.time);
}
}Q[N];
struct Change{int w,co;}C[N];
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
inline void add(Re x){ans+=!cnt[x]++;}
inline void del(Re x){ans-=!--cnt[x];}
int main(){
// freopen("123.txt","r",stdin);
in(n),in(T),BL=pow(n,2.0/3.0);
for(Re i=1;i<=n;++i)in(a[i]);
for(Re i=1;i<=T;++i){
scanf(" %c",&op);
in(x),in(y);
if(op=='Q')++TQ,Q[TQ]=(Query){x,y,TQ,TC};
else C[++TC]=(Change){x,y};
}
sort(Q+1,Q+TQ+1);
Re nowL=1,nowR=0,nowT=0;
for(Re i=1;i<=TQ;++i){
while(nowL<Q[i].l)del(a[nowL++]);
while(nowL>Q[i].l)add(a[--nowL]);
while(nowR>Q[i].r)del(a[nowR--]);
while(nowR<Q[i].r)add(a[++nowR]);
while(nowT<Q[i].time){
Re w=C[++nowT].w;
if(nowL<=w&&w<=nowR)del(a[w]),add(C[nowT].co);
swap(a[w],C[nowT].co);
}
while(nowT>Q[i].time){
Re w=C[nowT].w;
if(nowL<=w&&w<=nowR)del(a[w]),add(C[nowT].co);
swap(a[w],C[nowT--].co);
}
Ans[Q[i].id]=ans;
}
for(Re i=1;i<=TQ;++i)printf("%d\n",Ans[i]);
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LL long long
#define Re register int
using namespace std;
const int N=1e5+3,M=1e5+3,logN=17;
int n,m,x,y,o,T,op,id_O,A[N],V[N],W[N],B[N],head[N],last[N],first[N];
struct QAQ{int to,next;}a[N<<1];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
Re fu=0;x=0;char c=getchar();
while(c<'0'||c>'9')fu|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=fu?-x:x;
}
struct LCA{
int deep[N],ant[N][20];
inline void dfs(Re x,Re fa){
first[B[++B[0]]=x]=++id_O;
deep[x]=deep[ant[x][0]=fa]+1;
for(Re i=1;(1<<i)<=deep[x];++i)ant[x][i]=ant[ant[x][i-1]][i-1];
for(Re i=head[x];i;i=a[i].next)if(a[i].to!=fa)dfs(a[i].to,x);
last[B[++B[0]]=x]=++id_O;
}
inline int lca(Re x,Re y){
if(deep[x]<deep[y])swap(x,y);
for(Re i=logN;i>=0;--i)if(deep[ant[x][i]]>=deep[y])x=ant[x][i];
if(x==y)return x;
for(Re i=logN;i>=0;--i)if(ant[x][i]!=ant[y][i])x=ant[x][i],y=ant[y][i];
return ant[x][0];
}
}T1;
int BL,TQ,TC,vis[N],cnt[N];LL ans,Ans[M];
struct Query{
int l,r,id,lca,time;
inline bool operator<(const Query &O)const{
Re B1=l/BL,B2=O.l/BL,B3=r/BL,B4=O.r/BL;
return B1!=B2?B1<B2:(B3!=B4?B3<B4:time<O.time);
}
}Q[M];
struct Change{int w,co;}C[M];
inline void change(Re x){
vis[x]?ans-=(LL)V[A[x]]*W[cnt[A[x]]--]:ans+=(LL)V[A[x]]*W[++cnt[A[x]]],vis[x]^=1;
}
int main(){
freopen("123.txt","r",stdin);
in(n),in(m),in(T),BL=pow(n<<1,2.0/3.0);
for(Re i=1;i<=m;++i)in(V[i]);
for(Re i=1;i<=n;++i)in(W[i]);
for(Re i=1;i<n;++i)in(x),in(y),add(x,y),add(y,x);
for(Re i=1;i<=n;++i)in(A[i]);
T1.dfs(1,0);
for(Re i=1;i<=T;++i){
in(op),in(x),in(y);
if(op){
Re lca=T1.lca(x,y);
if(first[x]>first[y])swap(x,y);
if(lca==x)++TQ,Q[TQ]=(Query){first[x],first[y],TQ,0,TC};
else ++TQ,Q[TQ]=(Query){last[x],first[y],TQ,lca,TC};
}
else C[++TC]=(Change){x,y};
}
sort(Q+1,Q+TQ+1);
Re nowL=1,nowR=0,nowT=0;
for(Re i=1;i<=TQ;++i){
Re L=Q[i].l,R=Q[i].r,T=Q[i].time,lca=Q[i].lca;
while(nowL<L)change(B[nowL++]);
while(nowL>L)change(B[--nowL]);
while(nowR>R)change(B[nowR--]);
while(nowR<R)change(B[++nowR]);
while(nowT<T){
Re w=C[++nowT].w;
if(vis[w])change(w),swap(A[w],C[nowT].co),change(w);
else swap(A[w],C[nowT].co);
}
while(nowT>T){
Re w=C[nowT].w;
if(vis[w])change(w),swap(A[w],C[nowT].co),change(w);
else swap(A[w],C[nowT].co);
--nowT;
}
if(lca)change(lca);
Ans[Q[i].id]=ans;
if(lca)change(lca);
}
for(Re i=1;i<=TQ;++i)printf("%lld\n",Ans[i]);
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LL long long
#define Re register int
using namespace std;
const int N=4e4+3,M=1e5+3,INF=1e6+3,logN=16;
int n,m,o,x,y,T,BL,id_O,b[N],A[N],B[N<<1],head[N],last[N],first[N];
struct QAQ{int to,next;}a[N<<1];
inline void add(Re x,Re y){a[++o].to=y,a[o].next=head[x],head[x]=o;}
inline void in(Re &x){
Re fu=0;x=0;char c=getchar();
while(c<'0'||c>'9')fu|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=fu?-x:x;
}
struct LCA{
int deep[N],ant[N][20];
inline void dfs(Re x,Re fa){
first[B[++B[0]]=x]=++id_O;
deep[x]=deep[ant[x][0]=fa]+1;
for(Re i=1;(1<<i)<=deep[x];++i)ant[x][i]=ant[ant[x][i-1]][i-1];
for(Re i=head[x];i;i=a[i].next)if(a[i].to!=fa)dfs(a[i].to,x);
last[B[++B[0]]=x]=++id_O;
}
inline int lca(Re x,Re y){
if(deep[x]<deep[y])swap(x,y);
for(Re i=logN;i>=0;--i)if(deep[ant[x][i]]>=deep[y])x=ant[x][i];
if(x==y)return x;
for(Re i=logN;i>=0;--i)if(ant[x][i]!=ant[y][i])x=ant[x][i],y=ant[y][i];
return ant[x][0];
}
}T1;
struct Query{
int l,r,id,lca;
inline bool operator<(const Query &O)const{
Re B1=l/BL,B2=O.l/BL;
return B1!=B2?B1<B2:((B1&1)?r<O.r:r>O.r);
}
}Q[M];
int ans,vis[N<<1],Ans[M],cnt[INF];
inline void change(Re x){
vis[x]?ans-=!--cnt[A[x]]:ans+=!cnt[A[x]]++,vis[x]^=1;
}
int main(){
// freopen("123.txt","r",stdin);
in(n),in(T),BL=sqrt(n<<1);
for(Re i=1;i<=n;++i)in(A[i]),b[i]=A[i];
sort(b+1,b+n+1),m=unique(b+1,b+n+1)-b-1;
for(Re i=1;i<=n;++i)A[i]=lower_bound(b+1,b+m+1,A[i])-b;
m=n-1;while(m--)in(x),in(y),add(x,y),add(y,x);
T1.dfs(1,0);
for(Re i=1;i<=T;++i){
in(x),in(y);Re lca=T1.lca(x,y);
if(first[x]>first[y])swap(x,y);
if(lca==x)Q[i]=(Query){first[x],first[y],i,0};
else Q[i]=(Query){last[x],first[y],i,lca};
}
sort(Q+1,Q+T+1);
Re nowL=1,nowR=0;
for(Re i=1;i<=T;++i){
Re L=Q[i].l,R=Q[i].r,lca=Q[i].lca;
while(nowL<L)change(B[nowL++]);
while(nowL>L)change(B[--nowL]);
while(nowR>R)change(B[nowR--]);
while(nowR<R)change(B[++nowR]);
if(lca)change(lca);
Ans[Q[i].id]=ans;
if(lca)change(lca);
}
for(Re i=1;i<=T;++i)printf("%d\n",Ans[i]);
}
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LL long long
#define Re register int
using namespace std;
const int N=3e4+3,M=2e5+3;
int n,T,BL,ans,A[N],cnt[1000003],Ans[M];
struct Query{
int l,r,id;
inline bool operator<(const Query &O)const{
Re B1=l/BL,B2=O.l/BL;
return B1!=B2?B1<B2:((B1&1)?r<O.r:r>O.r);
}
}Q[M];
inline void in(Re &x){
int f=0;x=0;char c=getchar();
while(c<'0'||c>'9')f|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=f?-x:x;
}
inline void add(Re x){ans+=!cnt[x]++;}
inline void del(Re x){ans-=!--cnt[x];}
int main(){
in(n),BL=sqrt(n)+1;
for(Re i=1;i<=n;++i)in(A[i]);
in(T);
for(Re i=1;i<=T;++i)in(Q[i].l),in(Q[i].r),Q[i].id=i;
sort(Q+1,Q+T+1);Re nowL=1,nowR=0;
for(Re i=1;i<=T;++i){
while(nowR<Q[i].r)add(A[++nowR]);
while(nowR>Q[i].r)del(A[nowR--]);
while(nowL>Q[i].l)add(A[--nowL]);
while(nowL<Q[i].l)del(A[nowL++]);
Ans[Q[i].id]=ans;
}
for(Re i=1;i<=T;++i)printf("%d\n",Ans[i]);
}
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize(2)
#include<algorithm>
#include<cstdio>
#include<cmath>
#define Re register int
#define F(x,a,b) for(Re x=a;x<=b;++x)
#define LL long long
using std::sort;
const int N=5e4+3;
int n,q,t,L,R,ip,fu,len,gs[N],pt[N],co[N];LL ans,gcd,fz[N],fm[N];
struct QAQ{int l,r,id;}Q[N];
inline void in(Re &x){
x=fu=0;char c=getchar();
while(c<'0'||c>'9')fu|=c=='-',c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
x=fu?-x:x;
}
inline void sakura(Re p,Re x){ans-=(LL)gs[fu=co[p]]*gs[fu],gs[fu]+=x,ans+=(LL)gs[fu]*gs[fu];}
inline bool cmp(QAQ a,QAQ b){return pt[a.l]==pt[b.l]?a.r<b.r:a.l<b.l;}
inline LL gcd_(LL a,LL b){while(b^=a^=b^=a%=b);return a;}
int main(){
in(n),in(q),t=sqrt(n);
F(i,1,n)in(co[i]),pt[i]=i/t+1;
F(i,1,q)in(Q[i].l),in(Q[i].r),Q[i].id=i;
sort(Q+1,Q+q+1,cmp);
L=1,R=0;
F(i,1,q){
while(L<Q[i].l)sakura(L++,-1);
while(L>Q[i].l)sakura(--L,1);
while(R<Q[i].r)sakura(++R,1);
while(R>Q[i].r)sakura(R--,-1);
ip=Q[i].id;
if(Q[i].l==Q[i].r){fz[ip]=0,fm[ip]=1;continue;}
fz[ip]=ans-(len=Q[i].r-Q[i].l+1);
fm[ip]=(LL)len*(len-1);
gcd=gcd_(fz[ip],fm[ip]),fz[ip]/=gcd,fm[ip]/=gcd;
}
F(i,1,q)printf("%lld/%lld\n",fz[i],fm[i]);
}
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
const int u=40010;
int c[40][40][u],f[40][40],d[40][40],a[u],b[u],fa[u],fb[u],st[40],ed[40];
int n,m,t,l,tot,i,j,k,x,y,ans,L,R,cnt,num;
void prework()
{
t=(int)pow(n*1.0,1.0/3);
if(t) l=n/t;
for(i=1;i<=t;i++) st[i]=(i-1)*l+1,ed[i]=i*l;
if(ed[t]<n) st[t+1]=ed[t]+1,ed[++t]=n;
memcpy(fa,a,sizeof(a));
sort(fa+1,fa+n+1);
for(i=1;i<=n;i++)
if(i==1||fa[i]!=fa[i-1]) fb[++tot]=fa[i];
for(i=1;i<=n;i++) b[i]=lower_bound(fb+1,fb+tot+1,a[i])-fb;
for(i=1;i<=t;i++)
for(j=i;j<=t;j++)
{
for(k=st[i];k<=ed[j];k++) c[i][j][b[k]]++;
for(k=1;k<=tot;k++)
if(c[i][j][k]>f[i][j]||c[i][j][k]==f[i][j]&&k<d[i][j])
f[i][j]=c[i][j][k],d[i][j]=k;
}
}
inline void update(int i)
{
c[L][R][b[i]]++;
if(c[L][R][b[i]]>cnt||c[L][R][b[i]]==cnt&&b[i]<num) cnt=c[L][R][b[i]],num=b[i];
}
int solve(int x,int y)
{
int i,l,r;
if(x>y) swap(x,y);
for(i=1;i<=t;i++) if(x<=ed[i]) {l=i; break;}
for(i=t;i;i--) if(y>=st[i]) {r=i; break;}
if(l+1<=r-1) L=l+1,R=r-1; else L=R=0;
cnt=f[L][R],num=d[L][R];
if(l==r)
{
for(i=x;i<=y;i++) update(i);
for(i=x;i<=y;i++) c[L][R][b[i]]--;
}
else{
for(i=x;i<=ed[l];i++) update(i);
for(i=st[r];i<=y;i++) update(i);
for(i=x;i<=ed[l];i++) c[L][R][b[i]]--;
for(i=st[r];i<=y;i++) c[L][R][b[i]]--;
}
return fb[num];
}
int main()
{
cin>>n>>m;
for(i=1;i<=n;i++) scanf("%d",&a[i]);
prework();
for(i=1;i<=m;i++)
{
scanf("%d%d",&x,&y);
ans=solve((x+ans-1)%n+1,(y+ans-1)%n+1);
printf("%d\n",ans);
}
return 0;
}