#include <fstream>
#include <iostream>

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

struct node{
    short int info = 0;
    short unsigned l = 0, r = 0;
    node* fatherNode = NULL, *leftSubTree = NULL, *rightSubTree = NULL;
} *root;

int Tree_build(node* &thisN, int l, int r, node* fnode)
{
    node* crt; crt = new node;
    crt->fatherNode = fnode; crt->l = l, crt->r = r;
    if(l != r)
        crt->info = Tree_build(crt->leftSubTree, l, (l+r)/2, crt) +
                Tree_build(crt->rightSubTree, (l+r)/2+1, r, crt);
    else fin >> crt->info;
    if(l > r) thisN = NULL;
        else thisN = crt;

    if(thisN == NULL) return 0;
        return thisN->info;
}

void Tree_update(int a, int b)
{
    node* n = root;
    while(!(n->l == n->r)){
        n->info += b;
        if(a <= (n->l + n->r)/2) n = n->leftSubTree;
            else n = n->rightSubTree;
    }
    n->info += b;
}

int sum(int a, int b)
{
    node *n = root, *left, *right;
    int sl, sr;

    while(n->l != n->r){
        if(a > (n->l + n->r) / 2) n = n->rightSubTree;
        else if(b <= (n->l + n->r)/2) n = n->leftSubTree;
             else break;
    }

    if(n->l == n->r) return n->info;

    left = n->leftSubTree; right = n->rightSubTree;
    sl = left->info, sr = right->info;

    while(left->l != left->r){
        if(a > (left->l + left->r) / 2)
            sl -= left->leftSubTree->info,
            left = left->rightSubTree;
        else left = left->leftSubTree;
    }

    while(right->l != right->r){
        if(b <= (right->l + right->l) / 2)
            sr -= right->rightSubTree->info,
            right = right->leftSubTree;
        else right = right->rightSubTree;
    }

    return sl + sr;
}

node* leftmost(node* n)
{
    if(n == NULL) return n;
    while(n->leftSubTree != NULL) n = n->leftSubTree;
    return n;
}

int pozmin(int a)
{
    node *n = leftmost(root);

    while(n != NULL){
        if(a > n->info) n = n->fatherNode;
        else if(a < n->info){
            if(n->l == n->r) return -1;
            a -= n->leftSubTree->info,
            n = leftmost(n->rightSubTree);
        }
        else return n->r;
    }

    if(n == NULL) return -1;

}

int main()
{
    int n, m, i, a, b, t;

    fin >> n >> m;

    Tree_build(root, 1, n, NULL);

    for(i = 1; i <= m; i++){
        fin >> t;
        if(t == 0){ fin >> a >> b;Tree_update(a, b);}
        if(t == 1){ fin >> a >> b; fout << sum(a, b) << "\n";}
        if(t == 2){ fin >> a; fout << pozmin(a) << "\n";}
    }

    return 0;
}