#include<stdio.h>
#define Nmax 100009

int st,dr,q,m,n,t,i,x,y,type,a[Nmax];

void insert(int x,int y)
{
    while (x<=n)
    {
        a[x]+=y;
        x+=(x&(x^(x-1)));
    }
}

int query(int x)
{
    int s=0;
    while (x)
    {
        s+=a[x];
        x-=(x&(x^(x-1)));
    }
    return s;
}

int main()
{
    freopen("aib.in","r",stdin);
    freopen("aib.out","w",stdout);

    scanf("%d%d",&n,&t);
    for (i=1;i<=n;i++)
    {
        scanf("%d",&x);
        insert(i,x);
    }

    for (i=1;i<=t;i++)
    {
        scanf("%d",&type);
        if (type==0)
        {
            scanf("%d%d",&x,&y);
            insert(x,y);
        }
        if (type==1)
        {
            scanf("%d%d",&x,&y);
            printf("%d\n",query(y)-query(x-1));
        }
        if (type==2)
        {
            scanf("%d",&x);
            st=1;
            dr=n;
            while (st<=dr)
            {
                m=(st+dr)/2;
                q=query(m);

                if (q==x)
                {
                    printf("%d\n",m);
                    break;
                }
                if (q<x) st=m+1;
                    else dr=m-1;
            }
            if (q!=x) printf("-1\n");
        }
    }

}