#include <stdio.h>
#define zeros(x) ((x^(x-1))&x)
long a, b, i, k, n, m, v[100000];

void add(long x, long a);
long sum(long x);
long search(long a);

int main()
{
  freopen("aib.in", "r", stdin);
  freopen("aib.out", "w", stdout);
  scanf("%ld%ld", &n, &m);
  for (i=1; i<=n; i++)
  {
	scanf("%ld", &a);
	add(i, a);
  }//for i
  for (i=1; i<=m; i++)
  {
	scanf("%ld", &k);
	if (k==0)
	{
	  scanf("%ld%ld", &a, &b);
	  add(a, b);
	}//if 0
	if (k==1)
	{
	  scanf("%ld%ld", &a, &b);
	  printf("%ld\n", sum(b)-sum(a-1));
	}//if 1
	if (k==2)
	{
	  scanf("%ld", &a);
		printf("%ld\n", search(a));
	}//if 2
  }//for i
  return 0;
}//main

long search(long a)
{
	long jos=1, sus=n, mij=(1+n)/2, s;
	s=sum(mij);
	while ((jos<=sus)&&(s!=a))
	{
		mij=(jos+sus)/2;
		s=sum(mij);
		if (s>a)
			sus=mij-1;
		else
			if (s<a)
				jos=mij+1;
	}//while
	if (s!=a)
		return -1;
	else
		return mij;
}//search

void add(long x, long a)
{
  long i;
  for (i=x; i<=n; i+=zeros(i))
	v[i]+=a;
}//add

long sum(long x)
{
  long i, temp=0;
  for (i=x; i>0; i-=zeros(i))
	temp+=v[i];
  return temp;
}//sum