//#include "stdafx.h"
#include<stdio.h>
#define NMAX 100100
int x[NMAX],a,b,c,n,m,i;
int zero(int a)
{
	return (a^(a-1))&a;
}
void tip1(int a, int b)
{
	while (a<=n)
	{
		x[a]+=b;
		a+=zero(a);
	}
}
int tip2(int a)
{
	int s=0;
	while (a)
	{
		s+=x[a];
		a-=zero(a);
	}
	return s;
}
int tip3(int a)
{
	int in=1,sf=n,m;
	while (in<=sf)
	{
		m=(in+sf)>>1;
		if (tip2(m)<a)
			in=m+1;
		else
			sf=m-1;
	}
	sf++;
	m=tip2(sf);
	if (m!=a)
		return -1;
	else
		return sf;

}
int main()
{
	freopen("aib.in","r",stdin);
	freopen("aib.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (i=1;i<=n;i++)
	{
		scanf("%d",&a);
		tip1(i,a);
	}
	for (i=1;i<=m;i++)
	{
		scanf("%d",&a);
		if (a==0)
		{
			scanf("%d%d",&b,&c);
			tip1(b,c);
		} else
		if (a==1)
		{
			scanf("%d%d",&b,&c);
			printf("%d\n",tip2(c)-tip2(b-1));
		} else
		if (a==2)
		{
			scanf("%d",&b);
			printf("%d\n",tip3(b));
		}
	}

	return 0;
}