#include<cstdio>
#define zeros(x) (x&(-x))
using namespace std;

int aib[100002],n,k,i,x,durr,st,dr,mij,val,pos,tip,a,s,b;

void add(int x,int pos)
{
    int i;
    for(i=pos;i<=n;i+=zeros(i))
    {
        aib[i]+=x;
    }
}

int computionare(int pos)
{
    int i,valeur=0;
    for(i=pos;i>=1;i-=zeros(i))
    {
        valeur+=aib[i];
    }
    return valeur;
}

int main()
{
    freopen("aib.in","r",stdin);
    freopen("aib.out","w",stdout);
    scanf("%d%d",&n,&k);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&x);
        add(x,i);
    }
    for(i=1;i<=k;i++)
    {
        scanf("%d",&tip);
        if(tip==0)
        {
            scanf("%d%d",&pos,&val);
            add(val,pos);
        }
        if(tip==1)
        {
            scanf("%d%d",&a,&b);
            printf("%d\n",computionare(b)-computionare(a-1));
        }
        if(tip==2)
        {
            scanf("%d",&s);
            st=1;
            dr=n;
            while(st<=dr)
            {
                mij=(st+dr)/2;
                durr=computionare(mij);
                if(durr>s)
                {
                    dr=mij-1;
                }
                if(durr<s)
                {
                    st=mij+1;
                }
                if(durr==s)
                {
                    printf("%d\n",mij);
                    st=n+1;
                }
            }
            if(st!=n+1)
            {
                printf("-1");
            }
        }
    }
    return 0;
}