/*
#include <iostream>
#include <cmath>

using namespace std;

int main()
{double a;
int b;
cin>>a;
cout<<a<<"\n";
b=floor(a);
cout<<b;

    return 0;
}
*/
#include<cstdio>
using namespace std;
int v[100001],n,lo=1;

void up(int poz,int val)
{
    while(poz<=n)
    {
        v[poz]+=val;
        poz+=(poz&(poz-1))^poz;
    }
}
int down(int a)
{int b=0;
    while(a)
    {
        b+=v[a];
        a-=(a&(a-1))^a;
    }
    return b;
}
int jos(int a, int b)
{
    a=down(a-1);
    b=down(b);
    return b-a;
}

int caut(int s)
{int i=lo,st=1,dr=n;
for(i;i;i)
{   if(st==dr&&down(st)!=s)return -1;
    if(down(i)>s){dr=i-1;i=(st+i)/2;}
    else if (down(i)<s){st=i+1;i=(i+dr)/2+1; }
    else return i;
}

}

/*
int caut(int s)
{
    int a=0,i,step=lo*2;

    for(i=0;step;step>>=1)
    {
        if(i+step<=n)
        {
            if(v[i+step]<=s){s-=v[i+step];i+=step;}
        }

    }
    if(s)return -1;
    return i;

}
*/

int main()
{
    freopen("aib.in","r",stdin);
    freopen("aib.out","w",stdout);
    int m,i,j,a,b,q;
    scanf("%d%d",&n,&m);
    for(i=n;i;i/=2)lo*=2;
    lo/=2;
    for(i=1;i<=n;i++)
    {
        scanf("%d",&a);
        up(i,a);
    }
    for(i=0;i<m;i++)
    {
        scanf("%d",&q);
        if(q==0)
            {
                scanf("%d%d",&a,&b);
                up(a,b);
            }
        else if(q==1)
        {
            scanf("%d%d",&a,&b);
            a=jos(a,b);
            printf("%d\n",a);
        }
        else{
                scanf("%d",&a);
                a=caut(a);
                printf("%d\n",a);
            }
    }




    return 0;
}