#include <bits/stdc++.h>

using namespace std;
ifstream f("aib.in");
ofstream g("aib.out");
const int N=100101;
int aib[N],n,q,c,a,b,suma(int),mi,hi,lo;
void add(int,int);

int main()
{
    f>>n>>q;
    for(int i=1; i<=n; i++)
    {
        f>>a;
        add(a,i);

    }
    for(; q; q--)
    {
        f>>c>>a;
        if(c==0)
        {
            f>>b;
            add(b,a);
            continue;
        }
        if(c==1)
        {
            f>>b;
            g<<suma(b)-suma(a-1)<<'\n';
            continue;
        }
        if(suma(n)<a)
        {
            g<<"-1\n";
            continue;
        }
        int lo=0;
        int hi=n;
        while(hi-lo>1)
        {
            mi=(hi+lo)/2;
            if(suma(mi)<a)
                lo=mi;
            else
                hi=mi;
        }
        if(suma(hi)!=a)
            hi=-1;
        g<<hi<<'\n';

    }
    return 0;
}
void add(int v,int p)
{
    for(; p<=n; p+=p&(-p))
        aib[p]+=v;
}
int suma(int p)
{
    int val=0;
    for(; p; p-=p&(-p))
        val+=aib[p];
    return val;
}