#include <bits/stdc++.h>

using namespace std;

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

int aib[100005];
int n, x;
int q, tip, poz1, poz2, nr;

int lsb(int k){return (k&(-k));}

void update(int nod, int val){
    while(nod <= n){
        aib[nod] += val;
        nod += lsb(nod);
    }
}

int suma(int nod){
    int sum=0;
    while(nod > 0){
        sum += aib[nod];
        nod -= lsb(nod);
    }
    return sum;
}

int cb(int target){
    int sol, st=1, md, dr=n;
    while(st <= dr){
        md  = (dr-st)/2+st;
        sol = suma(md);

        if(sol == target)
            return md;

        if(sol < target)
            st=md+1;
        else
            dr=md-1;
    }

    return -1;
}

int main(){
    fin>>n>>q;
    for(int i=1; i <= n; i++){
        fin>>x;
        update(i, x);
    }

    for(int query=1; query <= q; query++){
        fin>>tip;

        if(tip == 0){
            fin>>poz1>>nr;
            update(poz1, nr);
        }else if(tip == 1){
            fin>>poz1>>poz2;
            fout<<suma(poz2) - suma(poz1-1)<<"\n";
        }else{
            fin>>nr;
            fout<<cb(nr)<<"\n";
        }
    }

    return 0;
}