// hmm se pare ca nu pot sa parsez citirea cum voiam... ill just try something and... hmm...
// (i didnt typo anything above did i?...)

#include <stdio.h>
#define MAXN 100100
#define MAXS 6*MAXN+5

int A[MAXN],n,m;
int p2[32],p1[MAXN];
char s[MAXS];

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;
}

int serci(int x)
{
	int i, k=p1[n];
    
	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()
{
	int i,j,x;
	
	fgets(s,32,stdin);
	
	n=0; m=0; j=0;
	
	while (s[j]>='0' && s[j]<='9')
		n=n*10+s[j++]-'0';
	
	j++;
	
	while (s[j]>='0' && s[j]<='9')
		m=m*10+s[j++]-'0';
	
	preparations();
	
	fgets(s,MAXS,stdin);
	
	for (i=1,j=0; i<=n; i++,j++)
	{
		x=0;
		while (s[j]>='0' && s[j]<='9')
			x=x*10+s[j++]-'0';
		
		update(i,x);
	}	
}

void rezolvare()
{
	int i,j,t,a,b,S;
	
	for (i=0; i<m; i++)
	{
		fgets(s,16*4,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;
}