#include <stdio.h>
#include <stdlib.h>
#define MAXN 100000
#define zeros(x) ((x^(x-1))&x)

int n, aib[MAXN+1];
inline void Add(int x, int quantity){
    for(int i=x;i<=n;i+=zeros(i))
        aib[i]+=quantity;
}

inline int Compute(int x){
    int rez=0;
    for(int i=x;i>0;i-=zeros(i)){
        rez+=aib[i];
    }
    return rez;
}

inline int BinarySearch(int val){
    int st=1, dr=n;
    while(dr-st>1){
        int m=Compute((st+dr)/2);
        if(m<val)
            st=(st+dr)/2+1;
        else
            dr=(st+dr)/2;
    }
    if(Compute(st)==val)
        return st;
    if(Compute(dr)==val)
        return dr;
    return -1;
}

int main(){
    FILE*fi,*fo;
    fi=fopen("aib.in","r");
    fo=fopen("aib.out","w");
    int m, x, t, a, b;
    fscanf(fi,"%d%d", &n, &m);
    for(int i=1;i<=n;i++){
        fscanf(fi,"%d", &x);
        Add(i, x);
    }
    for(int i=0;i<m;i++){
        fscanf(fi,"%d", &t);
        if(t==0){
            fscanf(fi,"%d%d", &a, &b);
            Add(a, b);
        }
        else if(t==1){
            fscanf(fi,"%d%d", &a, &b);
            fprintf(fo,"%d\n", Compute(b)-Compute(a-1));
        }
        else{
            fscanf(fi,"%d", &a);
            fprintf(fo,"%d\n", BinarySearch(a));
        }
    }
    fclose(fi);
    fclose(fo);
    return 0;
}