#include <cstdio>
#define lsb(x) x&(-x)

using namespace std;
int n, m, i, x, y, q, v[100005];
void add(int x, int w)
{
    int i;
    for(i=x;i<=n;i+=lsb(i))
        v[i]+=w;
}
int query(int x)
{
    int i, s;
    s=0;
    for(i=x;i>=1;i-=lsb(i))
        s+=v[i];
    return s;
}
int bin(int x)
{
    int i, p;
    for(p=1;p<=n;p<<=1);
    for(i=0;p;p>>=1)
        if(i+p<=n)
            if(x>=v[i+p])
            {
                i+=p;
                x-=v[i];
                if(!x) return i;
            }
    return -1;
}
int main()
{
    freopen("aib.in", "r", stdin);
    freopen("aib.out", "w", stdout);
    scanf("%d%d", &n, &m);
    for(i=1;i<=n;i++)
    {
        scanf("%d", &x);
        add(i, x);
    }
    for(i=1;i<=m;i++)
    {
        scanf("%d%d", &q, &x);
        if(q==0)
        {
            scanf("%d", &y);
            add(x, y);
        }
        else if(q==1)
        {
            scanf("%d", &y);
            printf("%d\n", query(y)-query(x-1));
        }
        else
        {
            printf("%d\n", bin(x));
        }
    }
    return 0;
}