#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;
}