// YES! i am an idiot! am parsat 1/2 din citire... si.. imi intra in balarii acu tre sa iau 100.. iar apoi sa rezolv parsarea cum tre!


#include <stdio.h>
#define MAXN 100100
#define MAXS 100000

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

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()
{
	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++)
	{
		x=0;
		while (c[j]>='0' && c[j]<='9')
		{
			x=x*10+c[j++]-'0';
			if (j==MAXS)
			{
				fgets(c,MAXS,stdin);
				j=0;				
			}
		}
		
		update(i,x);
	}	
}
*/
void citire()
{
	int i,x;
	
	scanf("%d%d",&n,&m);
	
	preparations();
	
	for (i=1; i<=n; i++)
	{
		scanf("%d",&x);		
		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++;
		scanf("%d",&t);
		
		if (t==0)
		{
			scanf("%d",&a);
			scanf("%d",&b);
		//	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)
		{
			scanf("%d",&a);
			scanf("%d",&b);
		//	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)
		{
			scanf("%d",&a);
		//	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;
}