#include <bits/stdc++.h>
using namespace std;

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

const int nmax = 100005;
int n, m, aib[nmax];

void Update(int pos, int val){
    while (pos <= n){
        aib[pos] += val;
        pos += (pos & (-pos));
    }
}

int Query(int pos){
    int sum = 0;
    while (pos > 0){
        sum += aib[pos];
        pos -= (pos & (-pos));
    }
    return sum;
}

int main(){
    fin >> n >> m;
    for (int i = 1; i <= n; ++i){
        int x;
        fin >> x;
        Update(i, x);
    }
    while (m--){
        int tip;
        fin >> tip;
        if (tip == 0){
            int x, y;
            fin >> x >> y;
            Update(x, y);
        }
        else if (tip == 1){
            int a, b;
            fin >> a >> b;
            fout << Query(b) - Query(a - 1) << "\n";
        }
        else{
            int a;
            fin >> a;
            int ans = -1, st = 1, dr = n;
            while (st <= dr){
                int mid = (st + dr) / 2;
                int s = Query(mid);
                if (s == a){
                    ans = mid;
                    dr = mid - 1;
                }
                else if (s < a){
                    st = mid + 1;
                }
                else{
                    dr = mid - 1;
                }
            }
            fout << ans << "\n";
        }
    }
    fin.close();
    fout.close();
    return 0;
}