#include<fstream>
#include<cmath>
#define lsb(x) (x&(-x))
using namespace std;
long n,m,i,v[100001],op,a,b,nr,x,mij,aux,val;
long s[100001];
void update(int x, int val)
{int i;
    for (i = x; i <= n; i += lsb(i))//lsb(i) returneaza 2^k,k=nr de 0 finale in baza 2 ale lui i
        v[i] += val;
}

int query(int x)
{int i, ret = 0;
    for (i = x; i > 0; i -= lsb(i))
        ret += v[i];
    return ret;
}

long search(int st,int dr)
{
	mij=(st+dr)/2;
	while(st<=dr)
	{    mij=(st+dr)/2;
	      x=query(mij);
		if(x<a) st=mij+1;
		  else               
		if(x>a) dr=mij-1;
		  else 
	    if(x==a) return mij;
	}
}
int main()
{
	ifstream f("aib.in");ofstream g("aib.out");
	f>>n>>m;
	for(i=1;i<=n;i++)
	{ 
	  f>>x; 
	  s[i]=s[i-1]+x; 
	  v[i]=s[i]-s[i-lsb(i)];//v[i] retine suma de la <i-2^k+1,i>,unde k=nr de o finale in reprezent binara a lui 
	}
	for(i=1;i<=m;i++)
	{
		f>>op;
		if(op<2)f>>a>>b;
		else f>>a;
		if(op==0)update(a,b);
		else
		if(op==1)g<<query(b)-query(a-1)<<"\n";
		else
		if(op==2)g<<search(1,n)<<"\n";
	}
	f.close();g.close();
return 0;}