//AIB operation type 2 in O(log N)

#include <fstream>

using namespace std;

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

const int Nmax = 100009;


int N; int M; unsigned int Aib[Nmax];

inline int Bit(const int &X){ return (X ^ (X - 1)) & X; }


void Update(int Pos, int Value){

    for( ; Pos <= N; Pos += Bit(Pos)) Aib[Pos] += Value;
}


void Read() {

    fin >> N >> M;

    for(int i = 1; i <= N; ++i){

        int X; fin >> X;
        Update(i, X);
    }

}

int Sum(int X){

    long long S = 0;

    for(; X > 0; X -= Bit(X) ) S += (long long)Aib[X];

    return S;
}

int BinarySearch(int X){

    int Pos = 0; int Step = 1;int S  = 0;

    for(; Step <= N ; (Step <<= 1));

    for(; Step; (Step >>=1)){
        if(Pos + Step <= N && Aib[Pos + Step] <= X){
            Pos += Step, X -= Aib[Pos];

            if(!X) return Pos;
        }
    }

    return -1;
}


int main() {

    Read ();

    while(M--){

        int type; int a, b;

        fin >> type;

        if(type == 0){ fin >> a >> b; Update(a, b);}

        if(type == 1){ fin >> a >> b; fout << Sum(b) - Sum(a - 1) <<'\n'; }

        if(type == 2){ fin >> a; fout << BinarySearch(a)<<'\n';  }

    }

    return 0;
}