template<class T> struct BIT {
int n;
vector<T> w;
BIT(int n, auto &in) : n(n), w(n + 1) { // 预处理填值
for (int i = 1; i <= n; i++) {
add(i, in[i]);
}
}
void add(int x, T v) {
for (; x <= n; x += x & -x) {
w[x] += v;
}
}
T ask(int x) { // 前缀和查询
T ans = 0;
for (; x; x -= x & -x) {
ans += w[x];
}
return ans;
}
T ask(int l, int r) { // 差分实现区间和查询
return ask(r) - ask(l - 1);
}
};/*
n n
S[x]= (x+1)*��A[i] - ��i*A[i]
i=1 i=1
*/
#include<cstdio>
#define LL long long
#define Re register int
const int N=1e6+3;
int n,x,y,z,T,op;
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;
}
struct BIT{
LL C1[N],C2[N];
inline void add(Re x,Re v){Re i=x;while(i<=n)C1[i]+=v,C2[i]+=(LL)x*v,i+=i&-i;}
inline void add(Re L,Re R,Re v){add(L,v),add(R+1,-v);}
inline LL ask(Re x){Re i=x;LL ans=0;while(i)ans+=(x+1)*C1[i]-C2[i],i-=i&-i;return ans;}
inline LL ask(Re L,Re R){return ask(R)-ask(L-1);}
}TR;
int main(){
in(n),in(T);
for(Re i=1;i<=n;++i)in(x),TR.add(i,i,x);
while(T--){
in(op),in(x),in(y);
if(op<2)in(z),TR.add(x,y,z);
else printf("%lld\n",TR.ask(x,y));
}
}
#include<cstdio>
#define LL long long
#define Re register int
const int N=5e5+3;
int n,x,y,z,T,op;
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;
}
struct BIT{
LL C[N];
inline void add(Re x,Re v){while(x<=n)C[x]+=v,x+=x&-x;}
inline void add(Re L,Re R,Re v){add(L,v),add(R+1,-v);}
inline LL ask(Re x){LL ans=0;while(x)ans+=C[x],x-=x&-x;return ans;}
}TR;
int main(){
in(n),in(T);
for(Re i=1;i<=n;++i)in(x),TR.add(i,i,x);
while(T--){
in(op),in(x);
if(op<2)in(y),in(z),TR.add(x,y,z);
else printf("%lld\n",TR.ask(x));
}
}
#include<cstdio>
#define LL long long
#define Re register int
const int N=5e5+3;
int n,x,y,T,op;
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;
}
struct BIT{
LL C[N];
inline void add(Re x,Re v){while(x<=n)C[x]+=v,x+=x&-x;}
inline LL ask(Re x){LL ans=0;while(x)ans+=C[x],x-=x&-x;return ans;}
inline LL ask(Re L,Re R){return ask(R)-ask(L-1);}
}TR;
int main(){
in(n),in(T);
for(Re i=1;i<=n;++i)in(x),TR.add(i,x);
while(T--){
in(op),in(x),in(y);
if(op<2)TR.add(x,y);
else printf("%ld\n",TR.ask(x,y));
}
}
/*
n m n m n m n m
s[x][y]=(x+1)*(y+1)*�� ��a[i][j] - (y+1)*�� ��a[i][j]*i - (x+1)*�� ��a[i][j]*j + �� ��a[i][j]*i*j
i=1 j=1 i=1 j=1 i=1 j=1 i=1 j=1
*/
#include<cstdio>
#define y1 yyyy
#define LL long long
#define Re register int
const int N=2048+3;
int n,m,x,x1,y1,x2,y2,op;
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;
}
struct BIT{
LL C1[N][N],C2[N][N],C3[N][N],C4[N][N];
inline void add(Re x,Re y,Re v){
Re i=x;
while(i<=n){
Re j=y;
while(j<=m)C1[i][j]+=v,C2[i][j]+=(LL)x*v,C3[i][j]+=(LL)y*v,C4[i][j]+=(LL)x*y*v,j+=j&-j;
i+=i&-i;
}
}
inline void add(Re x1,Re y1,Re x2,Re y2,Re z){
add(x1,y1,z),add(x1,y2+1,-z),add(x2+1,y1,-z),add(x2+1,y2+1,z);
}
inline LL ask(Re x,Re y){
Re i=x;LL ans=0;
while(i){
Re j=y;
while(j)ans+=(LL)(x+1)*(y+1)*C1[i][j]-(LL)(y+1)*C2[i][j]-(LL)(x+1)*C3[i][j]+C4[i][j],j-=j&-j;
i-=i&-i;
}
return ans;
}
inline LL ask(Re x1,Re y1,Re x2,Re y2){
return ask(x2,y2)-ask(x2,y1-1)-ask(x1-1,y2)+ask(x1-1,y1-1);
}
}TR;
int main(){
in(n),in(m);
while(~scanf("%d",&op)){
in(x1),in(y1),in(x2),in(y2);
if(op<2)in(x),TR.add(x1,y1,x2,y2,x);
else printf("%lld\n",TR.ask(x1,y1,x2,y2));
}
}
/*
(样例输入)
输入:
2 3 8
1 1 2 2 3 2
1 1 1 2 2 -3
2 1 1
2 1 2
2 1 3
2 2 1
2 2 2
2 2 3
输出
-3
-1
2
-3
-1
2
*/
#include<cstdio>
#define y1 yyyy
#define LL long long
#define Re register int
const int N=4096+3;
int n,m,T,x,x1,y1,x2,y2,op;
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;
}
struct BIT{
LL C[N][N];
inline void add(Re x,Re y,Re v){
while(x<=n){Re j=y;while(j<=m)C[x][j]+=v,j+=j&-j;x+=x&-x;}
}
inline void add(Re x1,Re y1,Re x2,Re y2,Re z){
add(x1,y1,z),add(x1,y2+1,-z),add(x2+1,y1,-z),add(x2+1,y2+1,z);
}
inline LL ask(Re x,Re y){
LL ans=0;
while(x){Re j=y;while(j)ans+=C[x][j],j-=j&-j;x-=x&-x;}
return ans;
}
}TR;
int main(){
in(n),in(m),in(T);
while(T--){
in(op),in(x1),in(y1);
if(op<2)in(x2),in(y2),in(x),TR.add(x1,y1,x2,y2,x);
else printf("%lld\n",TR.ask(x1,y1));
}
}
#include<cstdio>
#define y1 yyyy
#define LL long long
#define Re register int
const int N=4096+3;
int n,m,x1,y1,x2,y2,op;
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;
}
struct BIT{
LL C[N][N];
inline void add(Re x,Re y,Re v){
while(x<=n){Re j=y;while(j<=m)C[x][j]+=v,j+=j&-j;x+=x&-x;}
}
inline LL ask(Re x,Re y){
LL ans=0;
while(x){Re j=y;while(j)ans+=C[x][j],j-=j&-j;x-=x&-x;}
return ans;
}
inline LL ask(Re x1,Re y1,Re x2,Re y2){return ask(x2,y2)-ask(x2,y1-1)-ask(x1-1,y2)+ask(x1-1,y1-1);}
}TR;
int main(){
in(n),in(m);
while(~scanf("%d",&op)){
in(x1),in(y1),in(x2);
if(op<2)TR.add(x1,y1,x2);
else in(y2),printf("%lld\n",TR.ask(x1,y1,x2,y2));
}
}
#include<cstdio>
#define LL long long
#define Re register int
const int N=1e5+3;
int n,x,y,T,A[N];
inline void in(Re &x){
int f=0;x=0;char ch=getchar();
while(ch<'0'||ch>'9')f|=ch=='-',ch=getchar();
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
x=f?-x:x;
}
inline int max(Re a,Re b){return a>b?a:b;}
struct BIT{
int C[N];
inline void add(Re x,Re v){while(x<=n)C[x]=max(C[x],v),x+=x&-x;}
inline int ask(Re l,Re r){
Re ans=0;
while(l<=r){
while(r-(r&-r)>=l)ans=max(ans,C[r]),r-=r&-r;
ans=max(ans,A[r--]);
}
return ans;
}
}TR;
int main(){
in(n),in(T);
for(Re i=1;i<=n;++i)in(A[i]),TR.add(i,A[i]);
while(T--)in(x),in(y),printf("%d\n",TR.ask(x,y));
}
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#include<algorithm>
#include<cstdio>
#define Re register int
#define F(i,a,b) for(Re i=a;i<=b;++i)
#define lo(o) lower_bound(b+1,b+m+1,o)-b
#define P(x) if(op[i]==x)
using namespace std;
const int N=1e5+3,inf=2147483647;
int m,T,fu,C[N],a[N],b[N],Q[N],op[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 add(Re x,Re v){while(x<=m)C[x]+=v,x+=x&-x;}
inline int ask(Re x){
Re ans=0;
while(x>0)ans+=C[x],x-=x&-x;
return ans;
}
inline int ask_kth(Re k){
Re l=0,r=m;
while(l<r){
Re mid=l+r>>1;
if(ask(mid)>=k)r=mid;
else l=mid+1;
}
return b[l];
}
int main(){
in(T);
F(i,1,T){
in(op[i]),in(Q[i]);
if(op[i]!=4)b[++m]=Q[i];
}
sort(b+1,b+m+1),m=unique(b+1,b+m+1)-b-1;
F(i,1,T){
P(1)add(lo(Q[i]),1);
P(2)add(lo(Q[i]),-1);
P(3)printf("%d\n",ask(lo(Q[i])-1)+1);
P(4)printf("%d\n",ask_kth(Q[i]));
P(5)printf("%d\n",ask_kth(ask(lo(Q[i])-1)));
P(6)printf("%d\n",ask_kth(ask(lo(Q[i]))+1));
}
}
#pragma GCC optimize(3,"Ofast","inline")
#pragma GCC optimize(2)
#include<cstdio>
#define LL long long
#define Re register LL
#define F(a,b) for(i=a;i<=b;++i)
const int N=5e5+3,Np=2e7;
LL i,j,n,x,l,r,K,T,fu,cnt,c[N],C[N],pan[Np+1],pri[Np+1],phi[Np+1];char ch;
inline void in(Re &x){
x=fu=0;ch=getchar();
while(ch<'0'||ch>'9')fu|=ch=='-',ch=getchar();
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();x=fu?-x:x;
}
inline void add(Re x,Re k){while(x<=n)C[x]+=k,x+=x&-x;}
inline LL ask(Re x){Re tmp=0;while(x)tmp+=C[x],x-=x&-x;return tmp;}
inline LL mi(Re x,Re k,Re P){
Re s=1,ok=0,flag=0;ok|=(x>=P);x%=P;
while(k){
if(k&1){s*=x;flag|=(ok||s>=P);s%=P;}
x*=x;ok|=(x>=P);x%=P;k>>=1;
}
return s+(flag?P:0);
}
inline LL sakura(Re l,Re r,Re P){
if(P==1|l>r)return 1;
return mi(ask(l),sakura(l+1,r,phi[P]),P);
}
int main(){
for(i=2;i<=Np;++i){
if(!pan[i])pri[++cnt]=i,phi[i]=i-1;
for(j=1;j<=cnt;++j){
if(i*pri[j]>Np)break;
pan[i*pri[j]]=1;
if(i%pri[j])phi[i*pri[j]]=phi[i]*(pri[j]-1);
else{phi[i*pri[j]]=phi[i]*pri[j];break;}
}
}
in(n),in(T);
F(1,n)in(x),add(i,x-l),l=x;
while(T--){
in(K),in(l),in(r),in(x);
if(K<2)add(l,x),add(r+1,-x);
else printf("%lld\n",sakura(l,r,x)%x);
}
}