# include <fstream>
# define MAXN   100005
# define bns(i) ((-i)&i)
/*
    bns(i) = bitul nesemnificativ al lui i
    {
        - 1, daca i impar
        - 2^k, daca i este par, unde k nr nat
        - i, daca i este de forma 2^k, unde k nr nat
    }
*/
using namespace std;
ifstream fin("aib.in");
ofstream fout("aib.out");

int n, m, x, a, b, S, cod;
int arb[MAXN];

void Update(int inf, int pos) {
    if (pos > n)
        return;

    arb[pos] += inf;
    Update(inf, pos + bns(pos));
}

int Suma(int pos) {
    if (!pos)
        return 0;

    return arb[pos] + Suma(pos - bns(pos));
}

int Search(int S) {
    int st = 1,
        dr = n,
        mid,
        sum;
    while (st<=dr) {
        mid = st+(dr-st)/2;
        sum = Suma(mid);
        if (sum == S)
            return mid;
        if (sum > S)
            dr = mid-1;
        else
            st = mid+1;
    }
    return -1;
}

int main() {
    fin >> n >> m;
    for (int i=1; i<=n; ++i) {
        fin >> x;
        Update(x, i);
    }
    for (int i=1; i<=m; ++i) {
        fin >> cod;
        if (cod == 0) {
            fin >> a >> b;
            Update(b, a);
            continue;
        }

        if (cod == 1) {
            fin >> a >> b;
            fout << Suma(b) - Suma(a-1) << "\n";
            continue;
        }

        if (cod == 2) {
            fin >> S;
            fout << Search(S) << "\n";
        }
    }
    return 0;
}