#include <fstream>

using namespace std;

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

const int Nmax = 100005;
int n,aib[Nmax];

void update(int x, int y){
    int i;
    for(i=x;i<=n;i+=(i&(-i)))
        aib[i]+=y;
}
int query(int x){
    if(x == 0)
        return 0;
    int s = 0,i;
    for(i=x;i>0;i-=(i&(-i)))
        s+=aib[i];
    return s;
}
int bsearch(int x){
    int st = 1,dr = n,mid,sol = -1;
    while(st<=dr){
        mid = (st+dr)/2;
        int q = query(mid);
        if(q<=x){
            st = mid+1;
            if(q == x)
                sol = mid;
        }
        else
            dr = mid-1;
    }
    return sol;
}

int main()
{
    int m,i;
    fin >> n >> m;
    for(i=1;i<=n;i++){
        int x;
        fin >> x;
        update(i,x);
    }
    for(i=1;i<=m;i++){
        int t,x,y;
        fin >> t >> x;
        if(t == 0 || t == 1){
            fin >> y;
            if(t == 0)
                update(x,y);
            else
                fout << query(y)-query(x-1) << '\n';
        }
        else
            fout << bsearch(x) << '\n';
    }
    return 0;
}