#include <fstream>
#define DIM 100005
#define bit(x) (x&(-x))

using namespace std;

ifstream fin("aib.in");
ofstream fout("aib.out");

int aib[DIM];

int N,x,M;
int a,b,c;

void upd(int x,int poz){
    for(int i=poz;i<=N;i+=bit(i))
        aib[i] += x;
}

int sum(int poz){
    int s=0;
    for(int i=poz;i>0;i-=bit(i))
        s+=aib[i];
    return s;
}

int cautbin(int x){
    int p=1,u=N;

    while(p<=u){
        int mid=(p+u)>>1;
        int val=sum(mid);
        if(val==x)
            return mid;
        if(val>x)
            u=mid-1;
        else
            p=mid+1;
    }

    return -1;

}

int main(){

    fin >> N >> M;

    for(int i=1;i<=N;i++){
        fin >> x;
        upd(x,i);
    }

    while(M--){
        fin >> a >> b;

        if(a==0){
            fin >> c;
            upd(c,b);
            continue;
        }
        if(a==1){
            fin >> c;
            fout << sum(c) - sum(b-1) << "\n";
            continue;
        }

        fout << cautbin(b) << "\n";
    }

}