#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N=1e5+5;

const int mod=536870912;

int idx,op,n,m;

ll M,A;

struct data {

	int z[2];

	bool operator<(const data &u) const{return z[idx]<u.z[idx];}

}a[N];

struct node {int mid,mn[2],mx[2],sz;ll val,add=0,mul=1,sum=0;}T[N];

struct kd_tree {

	int nd,ls[N],rs[N];

	void Build(int x,int l,int r) {

		idx^=1;int idt(idx);

		int mid=(l+r)>>1;

		T[x].mid=mid;T[x].sz=1;

		nth_element(a+l,a+mid,a+r+1);

		T[x].mn[0]=T[x].mx[0]=a[mid].z[0];T[x].mn[1]=T[x].mx[1]=a[mid].z[1];

		if(l!=mid) {

			ls[x]=++nd;int L(ls[x]);

			Build(nd,l,mid-1),idx=idt;

			T[x].mn[0]=min(T[x].mn[0],T[L].mn[0]),T[x].mn[1]=min(T[x].mn[1],T[L].mn[1]);

			T[x].mx[0]=max(T[x].mx[0],T[L].mx[0]),T[x].mx[1]=max(T[x].mx[1],T[L].mx[1]);

			T[x].sz+=T[L].sz;

		}

		if(r!=mid) {

			rs[x]=++nd;int R(rs[x]);

			Build(nd,mid+1,r);

			T[x].mn[0]=min(T[x].mn[0],T[R].mn[0]),T[x].mn[1]=min(T[x].mn[1],T[R].mn[1]);

			T[x].mx[0]=max(T[x].mx[0],T[R].mx[0]),T[x].mx[1]=max(T[x].mx[1],T[R].mx[1]);

			T[x].sz+=T[R].sz;

		}

//		printf("%d pos=(%d,%d)  z0:[%d,%d]  z1:[%d,%d]\n",x,a[mid].z[0],a[mid].z[1],T[x].mn[0],T[x].mx[0],T[x].mn[1],T[x].mx[1]);

	}

	void mk_tree() {

		++nd;idx=0;

		Build(1,1,n);

	}

	inline void Up_mul(int x,ll w) {

		T[x].mul=T[x].mul*w%mod;T[x].add=T[x].add*w%mod;

		T[x].val=T[x].val*w%mod;T[x].sum=T[x].sum*w%mod;

	}

	inline void Up_add(int x,ll w) {

		T[x].add=(T[x].add+w)%mod;

		T[x].sum=(T[x].sum+T[x].sz*w)%mod;T[x].val=(T[x].val+w)%mod;

	}

	void P_dw(int x) {

		if(T[x].mul!=1) {

			if(ls[x])Up_mul(ls[x],T[x].mul);

			if(rs[x])Up_mul(rs[x],T[x].mul);

			T[x].mul=1;

		}

		if(T[x].add) {

			if(ls[x])Up_add(ls[x],T[x].add);

			if(rs[x])Up_add(rs[x],T[x].add);

			T[x].add=0;

		}

	}

	void P_up(int x) {T[x].sum=(T[ls[x]].sum+T[rs[x]].sum+T[x].val)%mod;}

	void Update(int x,int l,int r) {

		if(T[x].mx[op]<l||T[x].mn[op]>r) return;

		if(T[x].mn[op]>=l&&T[x].mx[op]<=r) {Up_mul(x,M),Up_add(x,A);return;}

		P_dw(x);

		int pz(a[T[x].mid].z[op]);

		if(pz>=l&&pz<=r) {T[x].val=(T[x].val*M+A)%mod;}

		if(ls[x]) Update(ls[x],l,r);

		if(rs[x]) Update(rs[x],l,r);

		P_up(x);

	}

	ll Ask(int x,int l,int r) {

		if(T[x].mx[op]<l||T[x].mn[op]>r) return 0;

		if(l<=T[x].mn[op]&&T[x].mx[op]<=r) {return T[x].sum;}

		P_dw(x);

		ll res(0);int pz(a[T[x].mid].z[op]);

		if(pz>=l&&pz<=r) {res=T[x].val;}

		if(ls[x]) res=(res+Ask(ls[x],l,r))%mod;

		if(rs[x]) res=(res+Ask(rs[x],l,r))%mod;

		return res;

	}

}KD;

int main() {

	scanf("%d%d",&n,&m);

	for(int i=1;i<=n;i++) {a[i].z[0]=i;scanf("%d",&a[i].z[1]);}

	KD.mk_tree();

	for(int i=1;i<=m;i++) {

		int opt,l,r;

		scanf("%d%d%d",&opt,&l,&r);

		if(!opt) {op=0;scanf("%lld%lld",&M,&A);KD.Update(1,l,r);}

		else if(opt==1) {op=1;scanf("%lld%lld",&M,&A);KD.Update(1,l,r);}

		else if(opt==2) {op=0;printf("%lld\n",KD.Ask(1,l,r));}

		else if(opt==3) {op=1;printf("%lld\n",KD.Ask(1,l,r));}

	}

	return 0;

}