#include<bits/stdc++.h>
#define ll long long
#define gc() (p1==p2&&(p2=(p1=b)+fread(b,1,n,stdin),p1==p2)?EOF:*p1++)
using namespace std;
namespace r{
	const int n=1000000;
	char *p1,*p2,b[n];
	inline int read(){
		int x=0,f=1;
		char c=gc();
		while(!isdigit(c)){
			if(c==45) f=-1;
			c=gc();
		}
		while(isdigit(c)){
			x=(x<<1)+(x<<3)+c-'0';
			c=gc();
		}
		return x*f;
	}
}
using namespace r;
namespace w{
	const int s=1000000;
	char b[s];
	int cnt=0;
	inline void write(ll x){
		if(x<0){
			x=-x;
			b[cnt++]=45;
			if(cnt==s) fwrite(b,1,cnt,stdout),cnt=0;
		}
		if(x>9) write(x/10);
		b[cnt++]=(x%10)|48;
		if(cnt==s) fwrite(b,1,cnt,stdout),cnt=0;
	}
	inline void space(){
		b[cnt++]=' ';
		if(cnt==s) fwrite(b,1,cnt,stdout),cnt=0;
	}
	inline void endl(){
		b[cnt++]='\n';
		if(cnt==s) fwrite(b,1,cnt,stdout),cnt=0;
	}
	inline void show(){
		if(cnt) fwrite(b,1,cnt,stdout),cnt=0;
	}
}
using namespace w;
namespace ldm{
	int n,q,v[300001];
	ll ans;
	struct node{
		ll v,maxx,lt;
	}a[1200001];
	inline void pushup(int x){
		a[x].v=a[x<<1].v+a[x<<1|1].v;
		a[x].maxx=max(a[x<<1].maxx,a[x<<1|1].maxx); 
	}
	inline void pushdown(int x,int l,int r){
		int mid=(l+r)>>1;
		if(a[x].lt){
			a[x<<1].lt+=a[x].lt;
			a[x<<1|1].lt+=a[x].lt;
			a[x<<1].maxx+=a[x].lt;
			a[x<<1|1].maxx+=a[x].lt;
			a[x<<1].v+=1ll*(mid-l+1)*a[x].lt;
			a[x<<1|1].v+=1ll*(r-mid)*a[x].lt;
			a[x].lt=0;
		}
	}
	inline void build(int x,int l,int r){
		if(l==r){
			a[x].v=a[x].maxx=v[l];
			return;
		}
		int mid=(l+r)>>1;
		build(x<<1,l,mid);
		build(x<<1|1,mid+1,r);
		pushup(x);
	}
	inline void modify(int x,int l,int r,int L,int R){
		if(r<L||l>R) return;
		if(l==r){
			a[x].v=(a[x].v+1)%65536;
			a[x].maxx=a[x].v;
			return;
		}
		if(l>=L&&r<=R){
			if(a[x].maxx<65535){
				a[x].maxx++;
				a[x].v+=1ll*(r-l+1);
				a[x].lt++;
				return;
			}
		}
		pushdown(x,l,r);
		int mid=(l+r)>>1;
		modify(x<<1,l,mid,L,R);
		modify(x<<1|1,mid+1,r,L,R);
		pushup(x);
	}
	inline void query(int x,int l,int r,int L,int R){
		if(r<L||l>R) return;
		if(l>=L&&r<=R){
			ans+=a[x].v;
			return;
		}
		pushdown(x,l,r);
		int mid=(l+r)>>1;
		query(x<<1,l,mid,L,R);
		query(x<<1|1,mid+1,r,L,R);
		pushup(x);
	}
	int main(){
		n=read(),q=read();
		for(int i=1;i<=n;i++){
			v[i]=read();
		}
		build(1,1,n);
		while(q--){
			int c=read(),l=read(),r=read();
			if(c==1){
				modify(1,1,n,l,r);
			}else{
				ans=0;
				query(1,1,n,l,r);
				write(ans);
				endl();
			}
		}
		show();
		return 0;
	}
}
int main(){
	ldm::main();
	return 0;
}