#include <fstream>

#define zeros(x) (x&(x^(x-1)))
#define NMAX 100010
using namespace std;
ofstream fout("aib.out");
ifstream fin("aib.in");

int aib[NMAX], a, b, o, m, n;

void add(int poz, int x){
    for(int i = poz; i <= n; i += zeros(i)){
        aib[i] += x;
    }
}

int sum(int x){
    int sum = 0;

    for(int i = x; i >= 1; i -= zeros(i)){
        sum += aib[i];
    }

    return sum;
}

int bsearch(int x){
    int st = 1;
    int dr = n;

    while(st <= dr){
        int mij = (st + dr) / 2;
        int aux = sum(mij);
        if(aux == x){
            return mij;
        }

        else if(x < aux) dr = mij - 1;
        else st = mij + 1;
    }

    return -1;
}

int main()
{
    fin >> n >> m;

    for(int i = 1; i <= n; i++){
        fin >> a;
        add(i, a);
    }

    for(int i = 1; i <= m; i++){
        fin >> o;

        if(o == 0){
            fin >> a >> b;
            add(a, b);
        }

        else if(o == 1){
            fin >> a >> b;
            fout << sum(b) - sum(a-1) << '\n';
        }

        else if(o == 2){
            fin >> a;
            fout << bsearch(a) << '\n';
        }
    }

    return 0;
}