#include <iostream>
#include <fstream>
#include <set>
#include <cstring>
#include <cstdlib>
#include <vector>

#if 1
#define pv(x) cout<<#x<<" = "<<x<<"; ";cout.flush()
#define pn cout<<endl
#else
#define pv(x)
#define pn
#endif

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

using ll = long long;
using ull = unsigned long long;
using ui = unsigned int;
#define pb push_back
#define mp make_pair
const int NMax = 1e5 + 5;
const int inf = 1e9 + 5;
const int mod = 9973;
using zint = int;

int N,M;
int aib[NMax];

void update(int,int);
int query(int);
int querySingle(int);
int findK(int);

int main() {
    in>>N>>M;
    for (int i=1;i <= N;++i) {
        int val;
        in>>val;
        update(i,val);
    }

    while (M--) {
        int tip,a,b;
        in>>tip>>a;

        if (tip == 0) {
            in>>b;
            update(a,b);
        }
        else if (tip == 1) {
            in>>b;

            if (a == b) {
                out<<querySingle(a)<<'\n';
            }
            else {
                out<<query(b) - query(a-1)<<'\n';
            }
        }
        else {
            out<<((a == 0) ? -1 : findK(a))<<'\n';
        }
    }

    in.close();out.close();
    return 0;
}

void update(int idx,int val) {
    while (idx <= N) {
        aib[idx] += val;
        idx += idx & (~idx + 1);
    }
}

int query(int idx) {
    int ans = 0;
    while (idx) {
        ans += aib[idx];
        idx = idx & (idx-1);
    }

    return ans;
}

int querySingle(int idx) {
    int val1 = aib[idx],
        pre = idx - 1,
        val2 = 0,
        lca = idx & (idx-1);

    while (pre != lca) {
        val2 += aib[pre];
        pre = pre & (pre-1);
    }

    return val1 - val2;
}

int findK(int sum) {
    int pos = 0,pw = 1;
    for(;pw <= N;pw <<= 1) ;
    pw >>= 1;

    while (pw) {
        if (pos + pw <= N && aib[pos+pw] <= sum) {
            sum -= aib[pos += pw];
        }

        pw >>= 1;
    }

    if (sum == 0) {
        return pos;
    }
    return -1;
}