#include<stdio.h>
int arb[100002];
int n,l;
void adauga(int k,int val)
{
int r=0;
while(k<=n)
{
arb[k]+=val;
while(!(k&(1<<r)))r++;
k+=1<<r;
r++;
}
}
int interogare(int k)
{
int s=0,r=0;
while(k>=1)
{
s+=arb[k];
while(!(k&(1<<r)))r++;
k-=1<<r;
r++;
}
return s;
}
int search(int k)
{
int st=1,dr=n,mid,query;
while(st<=dr)
{
mid=(st+dr)/2;
query=interogare(mid);
if( query == k )
return mid;
else if(query>k)
dr=mid-1;
else if(query<k)
st=mid+1;
}
return -1;
}
int main()
{ 
freopen("aib.in","r",stdin);
freopen("aib.out","w",stdout);
scanf("%d %d",&n,&l);
int a,b;
for(int i=1;i<=n;i++)
{
scanf("%d",&a);
adauga(i,a);
}
int c;
for(int i=1;i<=l;i++)
{
scanf("%d",&a);
if(a==0)
{
scanf("%d%d",&b,&c);
adauga(b,c);
}
else if(a==1)
{
scanf("%d%d",&b,&c);
printf("%d\n",interogare(c)-interogare(b-1));
}
else
{
scanf("%d",&b);
printf("%d\n",search(b));
}
}
}