#include<stdio.h>
int aib[100001], n, m;
int bit(int x)
{
	return (x&(x-1))^x;
}
void update(int a,int b)
{
	int i;
	
	for(i = a; i<=n ; i += bit(i))
	{
		aib[i] += b;
	}
}
int querry(int x)
{
	int s,i;
	for(i = x,s = 0; i>=1 ; i-=bit(i))
	{
		s += aib[i];
	}
	return s;
}
int search(int a)
{
	int left = 1, right = n, mid, s;
	while(left<=right)
	{
		mid = left + (right - left)/2;
		s = querry(mid);
		if(s == a)return mid;
		if(s<a)
		{
			left = mid+1;
		}
		else right = mid-1;
	}
	
	return -1;
}
int main()
{
	int a,b,tip;
	FILE*f = fopen("aib.in","r");
	FILE*g = fopen("aib.out","w");
	
	fscanf(f,"%d %d",&n,&m);
	
	for(a = 1; a<=n ; ++a)
	{
		fscanf(f,"%d",&b);
		update(a,b);
	}
	while(m--)
	{
		fscanf(f,"%d ",&tip);
		if(tip == 0)
		{
			fscanf(f,"%d %d",&a,&b);
			update(a,b);
		}
		if(tip == 1)
		{
			fscanf(f,"%d %d",&a,&b);
			fprintf(g,"%d\n",querry(b)-querry(a-1));
		}
		if(tip == 2)
		{
			fscanf(f,"%d ",&a);
			fprintf(g,"%d\n",search(a));
		}
	}
	fclose(f);
	fclose(g);
	return 0;
}