#include <bits/stdc++.h>

using namespace std;

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

int n,aib[100005],m;
void adaug(int x,int p) {
    for (;p<=n;p+=(p^(p-1))&p)
        aib[p]+=x;
}
int query(int x) {
    int ans=0;
    for (;x>0;x-=(x^(x-1))&x)
        ans+=aib[x];
    return ans;
}

int caut(int  x) {
    int p,u,m;
    p=1;
    u=n;
    while (p<=n) {
        m=(p+u)/2;
        if (query(m)<x) p=m+1;
        else if (query(m)>x) u=m-1;
        else return m;
    }
    return -1;
}

int main() {
    int i,x,q,y;
    f>>n>>m;
    for(i=1;i<=n;i++) {
        f>>x;
        adaug(x,i);
    }
    for (i=1;i<=m;i++) {
        f>>q;
        if (q==0) {
            f>>x>>y;
            adaug(y,x);
        }
        else {
            if (q==1) {
                f>>x>>y;
                g<<query(y)-query(x-1);
            }
            else {
                f>>x;
                g<<caut(x);
            }
            g<<'\n';
        }
    }
    return 0;
}