#include<fstream>
#define NMAX 100010

using namespace std;

ifstream f("aib.in");
ofstream g("aib.out");

int n, m, op, aux, nr, i, xx, yy, st, dr, mij, ok, a[NMAX], x, ss;

inline int ult(int x)
{
	return (x^(x-1))&x;
}

int suma(int st, int dr)
{
	int sum=0;
	for (;dr>=st; dr-=ult(dr))
		sum+=a[dr];
	return sum;
}

void update(int pz, long long val)
{
	for (; pz<=n; pz+=ult(pz)) a[pz]+=val;
}

int main()
{
	f>>n>>m;
	
	for (i=1; i<=n; ++i)
	{
		f>>x;
		xx=ult(i);
		a[i]=x+suma(i-xx+1, i-1);
	}	

	for (i=1; i<=m; ++i)
	{
		f>>op;
		if (op==1)
		{
			f>>xx>>yy;
			g<<suma(1, yy)-suma(1, xx-1)<<"\n";
		}
		else
			if (op==0)
			{
				f>>xx>>yy;
				update(xx, yy);
			}
			else 
			{
				f>>x;
				st=1; dr=n; ok=-1;
				while (st<=dr && ok==-1)
				{
					mij=(st+dr)>>1;
					ss=suma(1, mij);
					if (ss==x) ok=mij;
					else if (ss<x) st=mij+1;
					else dr=mij-1;
				}
				g<<ok<<"\n";
			}
	}
	f.close();
	g.close();
	return 0;
}