#include <bits/stdc++.h>

using namespace std;

int n, test, aib[100005];

void update(int idx, int x)
{
    while(idx <= n){
        aib[idx] += x;
        idx += (idx&-idx);
    }
}

int query(int x)
{
    int sol = 0;
    while(x){
        sol += aib[x];
        x -= (x&-x);
    }
    return sol;
}

int main()
{
    ifstream fin ("aib.in");
    ofstream fout ("aib.out");
    fin >> n >> test;
    for (int i = 1; i <= n; ++i){
        int x;
        fin >> x;
        update(i, x);
    }
    while(test--){
        int t;
        fin >> t;
        int a, b;
        switch(t){
            case 0:
                fin >> a >> b;
                update(a, b);
                break;
            case 1:
                fin >> a >> b;
                fout << query(b)-query(a-1) << "\n";
                break;
            case 2:
                fin >> a;
                int lo = 0, hi = n, m, ans = -1;
                for (m = (lo+hi)/2; lo <= hi; m = (lo+hi)/2){
                    b = query(m);
                    if(b == a)
                        ans = m;
                    if(b >= a)
                        hi = m-1;
                    else lo = m+1;
                }
                fout << ans << "\n";
                break;
        }
    }
    return 0;
}