#include <bits/stdc++.h>

using namespace std;

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

int v[100005], aib[100005];
int n, m;

int query (int p) {
    int sum=0;
    for (int i=p; i>0; ) {
        sum+=aib[i];
        i-=i&(-i);
    }
    return sum;
}

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

int main()
{
    fin.tie(0); fin.sync_with_stdio(false);
    fin>>n>>m;
    for (int i=1; i<=n; i++) fin>>v[i];
    for (int i=1; i<=n; i++) {
        update(i, v[i]);
    }
    int op, a, b;
    for (int i=1; i<=m; i++) {
        fin>>op;
        switch (op)
        {
        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 st=1, dr=n, best_sol=-1;
            while (st<=dr) {
                int mid = (st+dr) / 2;
                if (query(mid)<a) {
                    st=mid+1;
                }
                else if (query(mid)>=a) {
                    dr=mid-1;
                    if (query(mid)==a) best_sol=mid;
                }
            }
            fout<<best_sol<<'\n';
            break;
        }
    }
    return 0;
}