#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(a,b);
            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)
             g<<hi;
             else
                g<<-1;

    }
    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;
}