#include<stdio.h>
#include<string.h>
FILE*fin=fopen("aib.in","r");
FILE*fout=fopen("aib.out","w");
#define nm 100005
#define zero(x)((x^(x-1))&x)
int aib[nm],n,m;
int query(int poz)
{
int ans=0;
while(poz>0)
{
ans+=aib[poz];
poz-=zero(poz);
}
return ans;
}
void update(int poz,int nr)
{
while(poz<=n)
{
aib[poz]+=nr;
poz+=zero(poz);
}
}
int main()
{
int i,op,st,dr,mij,nr,poz,a,b,sum;
fscanf(fin,"%d%d",&n,&m);
memset(aib,0,sizeof(aib));
for(i=1;i<=n;i++)
{
fscanf(fin,"%d",&nr);
update(i,nr);
}
for(i=1;i<=m;i++)
{
fscanf(fin,"%d",&op);
if(op==0)
{
fscanf(fin,"%d%d",&poz,&nr);
update(poz,nr);
}
if(op==1)
{
fscanf(fin,"%d%d",&a,&b);
fprintf(fout,"%d\n",query(b)-query(a-1));
}
if(op==2)
{
fscanf(fin,"%d",&nr);
st=0;dr=n;
while(st<dr)
{
mij=(st+dr)/2;
sum=query(mij);
if(sum==nr)
{
st=mij;
break;
}
else if(sum<nr) st=mij+1;
else dr=mij-1;
}
fprintf(fout,"%d\n",st);
}
}
fclose(fin);
fclose(fout);
return 0;
}