#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int,int>;
#define pb push_back

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

const int N = 1e5+3;

int n, m, aib[N];

void add(int pos, int val){
    for (; pos <= n; pos += pos&-pos)
        aib[pos] += val;
}
int gets(int pos){
    int r = 0;
    for (; pos; pos -= pos&-pos)
        r += aib[pos];
    return r;
}

int main()
{
    fin >> n >> m;
    for (int i = 1; i <= n; i++) { int x; fin >> x; add(i, x); }
    while (m--){
        int T; fin >> T;
        if (!T){
            int a, b; fin >> a >> b;
            add(a, b);
        }
        else if (T == 1){
            int a, b; fin >> a >> b;
            if (a > b) swap(a, b);
            fout << gets(b) - gets(a-1) << '\n';
        }
        else {
            int a; fin >> a;
            int lo = 1, hi = n;
            bool ok = 0;
            while (lo <= hi){
                int mi = (lo + hi) / 2;
                int r = gets(mi);
                if (r == a) {ok = 1; fout << mi << '\n'; break;}
                else if (r < a) lo = mi + 1;
                else hi = mi - 1;
            }
            if (!ok) fout << "-1\n";
        }
    }

    return 0;
}