#include<cstdio>

#define zeros(x) ((x^(x-1))&x)

const int nmax=100005;

int n,m,aib[nmax];

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

inline int compute(int x){
    int s = 0;
    while(x){
        s += aib[x];
        x -= zeros(x);
    }

    return s;
}

int searchbin(int sum)
{
    int al,med,st=0,dr=n;
    while(st<=dr)
    {
        med=(st+dr)/2;
        al=compute(med);
        if(al==sum)
            return med;
        else if(al<sum)
            st=med+1;
        else
            dr=med-1;
    }
    return -1;
}

int main()
{
    freopen("aib.in","r",stdin);
    freopen("aib.out","w",stdout);
    int i,sum,op,x,y;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&x);
        add(i,x);
    }
    for(i=1;i<=m;++i)
    {
        scanf("%d",&op);
        if(op==0)
        {
            scanf("%d%d",&x,&y);
            add(x,y);
        }
        else if(op==1)
        {
            scanf("%d%d",&x,&y);
            printf("%d\n",(compute(y)-compute(x-1)));
        }
        else
        {
            scanf("%d",&sum);
            printf("%d\n",searchbin(sum));
        }
    }
}