// acum sunt relativ fericit cu programul... poate pe viitor voi mai optimiza cate ceva.. trebuie doar sa mai fac un miiic test.... hmmmm daca scap de p1....

#include <stdio.h>
#define MAXN 100005
#define MAXS 500000

int A[MAXN],n,m;
int p2[32];//,p1[MAXN];

/*
void update(int p, int x)
{
    while ( p <= n )  
    {  
        A[p] += x;  
 		p +=p1[p];
	}
}

int getsum(int p)
{
	int S=0;
	while ( p > 0 )  
    {  
        S+=A[p]; 
 		p -=p1[p];
	}
	return S;
}
*/

void update(int p, int x)
{
	int k;
    while ( p <= n )  
    {  
        A[p] += x;  
		k=0;
		while ( !( p & p2[k]) )
			k++;
 		p +=p2[k];
	}
}

int getsum(int p)
{
	int S=0,k=0;
	while ( p > 0 )  
    {  
        S+=A[p]; 
		k=0;
		while ( !( p & p2[k]) )
			k++;
 		p -=p2[k];
	}
	return S;
}

int serci(int x)
{
	int i, k=1;
    
	while (k<n)
		k<<=1;
    
	for( i=0; k; k>>=1)  
        if(i+k<=n)  
		{  
            if(x>=A[i+k])
			{
				i+=k; 
				x-=A[i];  
                if (!x )
					return i; 				
            }  
		}  
	
    return -1;  
}


void preparations()
{
	int i,k=0;
	
	p2[0]=1;
	for (i=1; i<=25; i++)
		p2[i]=p2[i-1]<<1;	
/*	
	for (i=1; i<=n; i++)
	{
		k=0;
		while (!(i & p2[k]))
			k++;
		p1[i]=p2[k];		
	}
*/
}

void citire()
{
	char c[MAXS]; int i,j,x;
	
	fgets(c,32,stdin);
	
	n=0; m=0; j=0;
	
	while (c[j]>='0' && c[j]<='9')
		n=n*10+c[j++]-'0';
	
	j++;
	
	while (c[j]>='0' && c[j]<='9')
		m=m*10+c[j++]-'0';
	
	preparations();
	
	fgets(c,MAXS,stdin);
	
	for (i=1,j=0; i<=n; i++,j++)
	{
		if (j==MAXS-1)
			{
				fgets(c,MAXS,stdin);
				j=0;				
			}
		x=0;
		while (c[j]>='0' && c[j]<='9')
		{
			x=x*10+c[j++]-'0';
			if (j==MAXS-1)
			{
				fgets(c,MAXS,stdin);
				j=0;				
			}
		}
		
		update(i,x);
	}	
}

void rezolvare()
{
	int i,j,t,a,b,S;
	char s[20];
	
	for (i=0; i<m; i++)
	{
		fgets(s,20,stdin); j=0; t=0; a=0; b=0; S=0;
	
		while (s[j]>='0' && s[j]<='9')
			t=t*10+s[j++]-'0';
		
		j++;
		
		if (t==0)
		{
			while (s[j]>='0' && s[j]<='9')
				a=a*10+s[j++]-'0';
			
			j++;
			
			while (s[j]>='0' && s[j]<='9')
				b=b*10+s[j++]-'0';
			
			update(a,b);			
		}
		if (t==1)
		{
			while (s[j]>='0' && s[j]<='9')
				a=a*10+s[j++]-'0';
			
			j++;
			
			while (s[j]>='0' && s[j]<='9')
				b=b*10+s[j++]-'0';
			
			S=getsum(b);
			S-=getsum(a-1);
			
			printf("%d\n",S);			
		}
		if (t==2)
		{
			while (s[j]>='0' && s[j]<='9')
				a=a*10+s[j++]-'0';
			
			S=serci(a);
			printf("%d\n",S);
		}		
	}	
}


int main()
{
	freopen("aib.in","r",stdin);
	freopen("aib.out","w",stdout);
	
	citire();
	rezolvare();
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}