#include <fstream>
#define N 100010
#define lsb(x) (x&(-x))


using namespace std;

ifstream f("aib.in");
ofstream g("aib.out");

int AIB[N],i,x,m,o,a,b,n;

void Update(int p,int v) {
    for (;p<=n;p+=lsb(p))
        AIB[p]+=v;
    return;
}

int Query(int p) {
    int v=0;
    for (;p>=1;p-=lsb(p))
        v+=AIB[p];
    return v;
}

int Search(int v) {
    int p=1,u=n,m,x;
    while (p<=u) {
        m=(p+u)/2;
        x=Query(m);
        if (x==v) return m;
        if (x<v) p=m+1;
            else u=m-1;
    }
    return -1;
}

int main() {
    f >> n >> m;
    for (i=1;i<=n;i++) {
        f >> x;
        Update(i,x);
    }
    for (i=1;i<=m;i++) {
        f >> o;
        if (o==0) {
            f >> a >> b;
            Update(a,b);
        }
        if (o==1) {
            f >> a >> b;
            g << (Query(b)-Query(a-1)) << '\n';
        }
        if (o==2) {
            f >> x;
            g << Search(x) << '\n';
        }
    }
    f.close();g.close();
    return 0;
}