#include<fstream>
#define NMAX 100010

using namespace std;

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

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

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

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

int main()
{
	f>>n>>m;
	
	for (i=1; i<=n; ++i)
	{
		aux=i;
		while (aux%2 == 0) ++k[i], aux=aux>>1;
	}
	
	for (i=1; i<=n; ++i)
	{
		f>>x;
		a[i]=x+suma(i-(1<<k[i])+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)/2;
					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;
}