#include <bits/stdc++.h>
using namespace std;
const int nmx = 1e5+1;
int a[nmx];
// when finished also run this using interval trees
// si cu binary search pe bits
int n;
#if 1
#define cin fin
#define cout fout
ifstream fin("aib.in");
ofstream fout("aib.out");
#endif
int query(int i){
    int sum = 0;
    for(;i>0;i-=i&-i)
        sum += a[i];
    return sum;
}

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

int main()
{
    int m;
    cin >> n >> m;
    for(int i=1;i<=n;i++){
        int x;
        cin >>x;
        update(i,x);
    }
    cout << query(n);
    while(m--){
        int op,x,y;
        cin >> op;
        if(op == 0){
            cin >> x >> y;
            update(x,y);
        }
        else if(op == 1){
            cin >> x >> y;
            cout << query(y)-query(x-1) << "\n";
        }
        else if(op == 2){
            cin >> x;
            int st = 0, dr = n+1;
            while(st<=dr){
                int md = (st+dr)/2;
                int res = query(md);
                if(res == x){
                    cout << md << "\n";
                    goto fin;
                }
                else if(res < x){
                    st = md+1;
                }
                else
                    dr = md-1;
            }
            cout << "-1\n";
            fin:{}
        }

    }

}