#define _CRT_SECURE_NO_WARNINGS
#include "stdio.h"

#define MAXN 100000

unsigned int v [MAXN+1];
unsigned int s [MAXN+1];
FILE *f,*g;
unsigned int n,m,lb;

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

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

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

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

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

void sum_find(int x,int sum)
{

}

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

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

int main()
{
	unsigned int 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]();
	}

}