#include <fstream>
#include <stdio.h>

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

int arb[100010], n, m, a, b, x, t;

void update(int x, int poz, int nod, int st, int dr)
{
    arb[nod] += x;

    if(st == dr) return;

    if(poz > (st+dr)/2){
        update(x, poz, nod*2 + 1, (st + dr)/2 + 1, dr);
    }

    else update(x, poz, nod*2, st, (st+dr)/2);
}

int sum(int x, int y, int nod, int st, int dr)
{
    if(st == x && dr == y){
        return arb[nod];
    }

    int nr1 = 0;
    int nr2 = 0;

    if(a > (st+dr)/2)
    {
        nr1 = sum(x, y, nod*2+1, (st+dr)/2 + 1, dr);
    }

    else if(b <= (st+dr)/2)
    {
        nr1 = sum(x, y, nod*2, st, (st+dr)/2);
    }

    else{
        nr1 = sum((st+dr)/2 + 1, y, nod*2+1, (st+dr)/2 + 1, dr);
        nr2 = sum(x, (st+dr)/2, nod*2, st, (st+dr)/2);
    }

    int s = nr1 + nr2;

    return s;
}

int case2(int a, int nod, int st, int dr)
{
    if(arb[nod] == a){
        return dr;
    }

    if(st == dr) return -1;

    int sum = 0;
    if(a <= arb[nod*2]){
        sum = case2(a, nod*2, st, (st+dr)/2);
    }

    else{
        sum = case2(a-arb[nod*2], nod*2+1, (st+dr)/2 + 1, dr);
    }

    return sum;
}

int main()
{
    freopen("aib.in", "r", stdin);
    scanf("%d%d", &n, &m);

    for(int i = 1; i <= n; i++){
        scanf("%d", &x);
        update(x, i, 1, 1, n);
    }

    for(int i = 1; i <= m; i++){
        scanf("%d", &t);

        if(t == 0){
            scanf("%d%d", &a, &b);
            update(b, a, 1, 1, n);
        }

        else if(t == 1){
            scanf("%d%d", &a, &b);
            fout << sum(a, b, 1, 1, n) << '\n';
        }

        else{
            scanf("%d", &a);
            fout << case2(a, 1, 1, n) << '\n';
        }
    }

    return 0;
}