#define _CRT_SECURE_NO_WARNINGS
#include "stdio.h"

#define MAXN 100001
#define MAXA 10000
typedef unsigned int DWORD;

DWORD v [MAXN];
DWORD s [MAXN];
FILE *f,*g;
DWORD n,m,lb;

DWORD get_bit(DWORD x)
{
	DWORD p = 1;
	while(! (x&p))
		p<<=1;
	return p;
}

DWORD get_last_bit(DWORD x)
{
	DWORD p = 1 , m=0;
	while(p <= x)
	{
		if(p&x)
			m = p;
		p<<=1;
	}
	return m;
}

void c0(void)
{
	DWORD a,b,p;
	fscanf(f,"%d %d",&a,&b);
	p = a;
	v[p] += b;
	while(p<=n)
	{
		s[p] += b;
		p += get_bit(p);
	}
}

DWORD sum(int x)
{
	DWORD sum;
	sum = 0;
	while(x)
	{
		sum += s[x];
		x-= get_bit(x);
	}
	return sum;
}

void c1(void)
{
	DWORD a,b;
	fscanf(f,"%d %d",&a,&b);
	fprintf(g,"%d\n",sum(b) - sum(a-1));
}

void c2(void)
{
	DWORD a,p,nr;
	fscanf(f,"%d",&a);
	if(a == 0)
	{
		fprintf(g,"-1\n");
		return;
	}
	p = lb;
	nr = 0;
	while(a && p)
	{
		if(((p|nr)<= n)&&(s[p|nr]<=a))
		{
			nr |=p;
			a -= s[nr];
		}
		p>>=1;
	}
	if(a == 0)
		fprintf(g,"%d\n",nr);
	else
		fprintf(g,"-1\n");
}

void (*cmds[3])(void);

int main()
{
	DWORD i,j,b,sum,c;
	f = fopen("aib.in","r"); 
	g = fopen("aib.out","w");
	cmds[0] = c0;
	cmds[1] = c1;
	cmds[2] = c2;

	fscanf(f,"%d %d",&n,&m);
	lb = get_last_bit(n);
	for(i=1;i<=n;i++)
	{
		fscanf(f,"%d",&v[i]);
		b = get_bit(i);
		sum = v[i];
		for(j = 1; j< b; j<<=1)
			sum += s[i-j];
		s[i] = sum;
	}

	for(i=0;i<m;i++)
	{
		fscanf(f,"%d",&c);
		cmds[c]();
	}

}