#include <cstdio>
#define NMax 100000

int aib[NMax+1];
int N;

void Update(int p, int x)
{
    while(p <= N)
    {
        aib[p] += x;
        p = p + ( p & (-p) );
    }
}

int Query(int p)
{
    int res=0;
    while(p > 0)
    {
        res += aib[p];
        p = p - ( p & (-p) );
    }
    return res;
}

int CautBin(int x)
{
    int st,dr,mid,f;

    for(f = -1, st = 1, dr = N; st <= dr; )
    {
        mid = (st+dr)/2;
        if( Query(mid) > x ) dr = mid-1;
        else if( Query(mid) < x ) st = mid+1;
        else{ f = mid; dr = mid-1; }
    }
    return f;
}

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

    int i,M,t,x,a,b;

    scanf("%d %d",&N,&M);
    for(i = 1; i <= N; ++i)
    {
        scanf("%d",&x);
        Update(i,x);
    }

    while(M--)
    {
        scanf("%d",&t);
        if(!t){
            scanf("%d %d",&a,&b);
            Update(a,b);
        }
        else if(t==1){
            scanf("%d %d",&a,&b);
            printf("%d\n", Query(b) - Query(a-1) );
        }
        else{
            scanf("%d",&x);
            printf("%d\n", CautBin(x) );
        }
    }


return 0;
}