#include <stdio.h>

using namespace std;

int v[100005],n,m;

int least_sgn(int n)
{
    return ((n&(n-1))^n);
}

void add(int x, int y)
{
    while(x<=n)
    {
        v[x]+=y;
        x+=least_sgn(x);
    }
}

int sum(int x)
{
    int s=0;
    while(x)
    {
        s+=v[x];
        x=x-least_sgn(x);
    }
    return s;
}

int cb(int st, int dr, int x)
{
    if(st>dr) return -1;
    int m=(st+dr)>>1,s=sum(m);
    if(s==x) return m;
    else if(x<s) return cb(st,m-1,x);
    else return cb(m+1,dr,x);
}

int main()
{
    freopen("aib.in","r",stdin);
    freopen("aib.out","w",stdout);
    int i,t,a,b;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&a);
        add(i,a);
    }
    for(i=0;i<m;i++)
    {
        scanf("%d",&t);
        if(t==0)
        {
            scanf("%d%d",&a,&b);
            add(a,b);
        }
        else if(t==1)
        {
            scanf("%d%d",&a,&b);
            printf("%d\n",sum(b)-sum(a-1));
        }
        else
        {
            scanf("%d",&a);
            b=-1;
            b=cb(1,n,a);
            printf("%d\n",b);
        }
    }
    return 0;
}