#include <iostream>
#include <cstdio>
using namespace std;
int n,aib[100001],log2;
int zer(int x)
{
return (x&(x-1))^x;
}
void build(int a,int poz)
{
int i;
for(i=poz;i<=n;i+=zer(i))aib[i]+=a;
}
int jos(int poz)
{
int i,x=0;
for(i=poz;i>0;i-=zer(i))x+=aib[i];
return x;
}
int bin(int val)
{int i,g=0,j=0;
for(i=log2;i>0;i>>=1)
if(j+i<=n&&aib[j+i]+g<=val)
{
j+=i;
g+=aib[j];
}
if(g==val)return j;
return -1;
}
int main()
{freopen("aib.in","r",stdin);
freopen("aib.out","w",stdout);
int m,i,j,a,b;
scanf("%d%d",&n,&m);
for(log2=1;log2<n;log2<<=1);
for(i=1;i<=n;i++)
{
scanf("%d",&j);
build(j,i);
}
for(i=1;i<=m;i++)
{
scanf("%d",&j);
if(j==0)
{
scanf("%d%d",&a,&b);
build(b,a);
}
else if(j==1)
{
scanf("%d%d",&a,&b);
j=jos(b)-jos(a-1);
printf("%d\n",j);
}
else
{
scanf("%d",&a);
printf("%d\n",bin(a));
}
}
return 0;
}