#include<bits/stdc++.h>
using namespace std;
int n,m,q;
const int mod = 65536;
struct Segment_tree
{
	long long a[300005];
	int cnt;
	struct node
	{
		long long sum,lazy,mx;
		int lson,rson;
	}tree[600005];
	void push_up(int k1)
	{
		tree[k1].mx = max(tree[tree[k1].lson].mx,tree[tree[k1].rson].mx);
		tree[k1].sum = tree[tree[k1].lson].sum + tree[tree[k1].rson].sum;
	}
	void build_tree(int &k1,int l,int r)
	{
		k1 = ++cnt;
		if(l == r)
		{
			tree[k1].sum = a[l];
			tree[k1].mx = a[l];
			return;
		}
		int mid = (l + r) / 2;
		build_tree(tree[k1].lson,l,mid);
		build_tree(tree[k1].rson,mid + 1,r);
		push_up(k1);
	}
	void pushdown(int k1,int l,int r)
	{
		int mid = (l + r) >> 1;
		tree[tree[k1].lson].lazy += tree[k1].lazy;
		tree[tree[k1].rson].lazy += tree[k1].lazy;
		tree[tree[k1].lson].sum += (mid - l + 1) * tree[k1].lazy;
		tree[tree[k1].rson].sum += (r - mid) * tree[k1].lazy;
		tree[tree[k1].lson].mx += tree[k1].lazy;
		tree[tree[k1].rson].mx += tree[k1].lazy;
		tree[k1].lazy = 0;
	}
	void update(int k1,int l,int r,int x,int y)
	{
		if(l == r)
		{
			tree[k1].sum = (tree[k1].sum + 1) % mod;
			tree[k1].mx = tree[k1].sum;
			tree[k1].lazy++;
			return;
		}
		if(x <= l && r <= y && tree[k1].mx < mod - 1)
		{
			tree[k1].sum += (r - l + 1);
			tree[k1].mx++;
			tree[k1].lazy++;
			return;
		}
		pushdown(k1,l,r);
		int mid = (l + r) >> 1;
		if(x <= mid) update(tree[k1].lson,l,mid,x,y);
		if(y > mid) update(tree[k1].rson,mid + 1,r,x,y);
		push_up(k1); 
	}
	long long query(int k1,int l,int r,int x,int y)
	{
		if(l == r)
		{
			tree[k1].sum %= mod;
			tree[k1].mx = tree[k1].sum;
			return tree[k1].sum;
		}
		if(x <= l && r <= y && tree[k1].mx < mod) return tree[k1].sum;
		pushdown(k1,l,r);
		int mid = (l + r) >> 1;
		long long ans = 0;
		if(x <= mid) ans += query(tree[k1].lson,l,mid,x,y);
		if(y > mid) ans += query(tree[k1].rson,mid + 1,r,x,y);
		push_up(k1);
		return ans;
	}
}t;
signed main()
{
	scanf("%d%d",&n,&m);
	for(int i = 1;i <= n;i++) scanf("%lld",&t.a[i]);
	t.build_tree(t.tree[0].lson,1,n); 
	for(int i = 1;i <= m;i++)
	{
		int opt;
		scanf("%d",&opt);
		if(opt == 1)
		{
			int x,y;
			scanf("%d%d",&x,&y);
			t.update(1,1,n,x,y);
		}
		else
		{
			int x,y;
			scanf("%d%d",&x,&y);
			printf("%lld\n",t.query(1,1,n,x,y));
		}
	}
	return 0;
}