#include <iostream>
#include <fstream>
using namespace std;
const int Maxx=1e5+2;
ifstream fin("aib.in");
ofstream fout("aib.out");
int n,i,querry;
int aib[Maxx],x;
int type,a,b;
void update(int poz,int val);
int gb(int n);
int sum(int idx);
int src(int sm);
int query(int a,int b);
int main() {
    fin>>n>>querry;
    for (i=1;i<=n;++i){
        fin>>x;
        update(i,x);
    }
    for (;querry;--querry){
        fin>>type;
        if (type==0){
            fin>>a>>b;
            update(a,b);
        } else if (type==1){
            fin>>a>>b;
            fout<<query(a,b)<<"\n";
        } else {
            fin>>a;
            fout<<src(a)<<"\n";
        }
    }
    return 0;
}
int gb(int n){
    return (n & -n);
}
int sum(int idx){
    int i,ret=0;
    for (i=idx;i>0;i-=gb(i)){
        ret+=aib[i];
    }
    return ret;
}
void update(int poz,int val){
    int i;
    for (i=poz;i<=n;i+=gb(i)){
        aib[i]+=val;
    }
}
int query(int a,int b){
    return sum(b)-sum(a-1);
}
int src(int sm){
    int act,st=1,dr=n,mid;
    while (st<=dr){
        mid=(st+dr)>>1;
        act=sum(mid);
        if (act<sm){
            st=mid+1;
        } else {
            dr=mid-1;
        }
    }
    if (sum(st)==sm) return st;
    return -1;
}