#include <bits/stdc++.h>

using namespace std;
ifstream fin("aib.in");
ofstream fout("aib.out");
int n, q, aib[100010];

inline void update(int x, int val) {
    for(int i=x; i<=n; i+=(i&(-i))) aib[i] += val;
}

inline int query(int x) {
    int rez = 0;
    for(int i=x; i>=1; i-=(i&(-i))) rez += aib[i];
    return rez;
}

int main()
{
    fin >> n >> q;
    for(int i=1; i<=n; i++) {
        int x; fin >> x;
        update(i, x);
    }
    while(q--) {
        int tip; fin >> tip;
        if(tip == 0) {
            int a, b; fin >> a >> b;
            update(a, b);
        }
        else if(tip == 1) {
            int a, b; fin >> a >> b;
            fout << query(b) - query(a - 1) << '\n';
        }
        else {
            int a; fin >> a;
            int st = 1, dr = n, sol = -1;
            while(st <= dr) {
                int mid = (st + dr) / 2;
                int x = query(mid);
                if(x == a) {
                    if(sol == -1) sol = mid;
                    else sol = min(sol, mid);
                    dr = mid - 1;
                }
                else if(x < a) st = mid + 1;
                else dr = mid - 1;
            }
            fout << sol << '\n';
        }
    }

    return 0;
}