#include <bits/stdc++.h>

using namespace std;

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

int n, m;
int aib[100005];

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

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

int main()
{
    fin.tie(0); fin.sync_with_stdio(false);
    fin>>n>>m;
    for (int i=1; i<=n; i++) {
        int x; fin>>x;
        update(i, x);
    }
    while (m--) {
        int op, a, b;
        fin>>op; 
        if (op==0) {
            fin>>a>>b;
            update(a, b);
        }
        if (op==1) {
            fin>>a>>b;
            int qst = query(a-1), qfin = query(b);
            int sum = qfin - qst;
            // cout << qfin <<' '<<qst<<' '<< sum<<endl;
            fout<<sum<<'\n';
        }
        if (op==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';
        }
    }
    return 0;
}