#include <bits/stdc++.h>
#define ll long long
using namespace std;
ifstream fin ("aib.in");
ofstream fout ("aib.out");

vector<ll> aib, v;

int lsb(int x)
{
    return x & (-x);
}

void update (int x, int add)
{
    for (int i = x; i < aib.size(); i += lsb(i)) {
        aib[i] += add;
    }
}

ll query (int x)
{
    ll sum = 0;
    for (int i = x; i > 0; i -= lsb(i)) {
        sum += aib[i];
    }
    return sum;
}

int cbin (ll s) {
    int ans = 0;
    ll sum_ans = 0;
    for (int pas = (1 << 18); pas > 0; pas /= 2) {
        if (ans + pas >= aib.size()) {continue;}
        if (sum_ans + aib[ans + pas] < s) {
            ans += pas;
            sum_ans += aib[ans];
        }
    }
    return ans + 1;
}

int main()
{
    int n, q; fin >> n >> q;
    aib.resize(n + 1);
    v.resize(n + 1);
    
    for (int i = 1; i <= n; i++) {
        fin >> v[i];
        update(i, v[i]);
    }

    while (q--) {
        int a, c;
        fin >> c >> a;
        if (c == 0) {
            int b;
            fin >> b;
            update(a, b);
        }
        else if (c == 1) {
            int b;
            fin >> b;
            fout << query(b) - query(a - 1) << '\n';
        }
        else {
            int rez = cbin(a);
            if (query(rez) == a) {
                fout << rez << '\n';
            }
            else {
                fout << "-1\n";
            }

        }
    }

    return 0;
}