#include <fstream>

#define max_n 100001

using namespace std;

int v[max_n],i,n,m,x,a,b,c;
bool ok1;

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

int bitul(int x) {
    return ((-x)&x);
}

void adauga(int x, int p) {
     while (p<=n) {
        v[p]+=x;
        p+=bitul(p);
    }
}

int suma (int a) {
    int rez=0;
    while (a>0) {
        rez+=v[a];
        a-=bitul(a);
    }
    return rez;
}

void caut_bin(int a) {
    int st,dr,m,s;
    st=1; dr=n;
    while (st<=dr) {
        m=(st+dr)/2;
        s=suma(m);
        if (s==a) {
           ok1=false;
           x=m;
           return;
        }
        else
        if (s<a) st=m+1;
        else dr=m-1;
    }
}

int main () {
   in >> n >> m;
   for (i=1; i<=n; i++) {
       in >> x;
       adauga(x,i);
    }

   for (i=1; i<=m; i++) {
       in >> c;
       if (c==0) {
           in >> a >> b;
           adauga(b,a);
       }
       else
       if (c==1) {
           in >> a >> b;
           x=suma(b)-suma(a-1);
           out << x << '\n';
       }
       else {
           in >> a;
           ok1=true;
           caut_bin(a);
           if (ok1==true) x=-1;
           out << x << '\n';
           }
    }
    return 0;
}