#include <bits/stdc++.h>

using namespace std;
ifstream fin("aib.in");
ofstream fout("aib.out");
const int Nmax=100001;
int aib[Nmax],n,m;
int bit(int x)
{
    return x&(-x);
}
void update(int val,int pos)
{
    for(int i=pos;i<=n;i+=bit(i)) aib[i]+=val;
}
int sum(int poz)
{
    int sum=0;
    for(;poz>=1;poz-=bit(poz)) sum+=aib[poz];
    return sum;
}
int querry(int val)
{
     int step,best;
     for(step=1;step<=n;step<<=1);
     for(best=0;step;step>>=1)
     {
         if(best+step<=n && sum(best+step)<val) best+=step;
     }
     if(sum(best+1)==val) return best+1;
     else return -1;
}
int main()
{
    int i,x,op,a,b;
    fin>>n>>m;
    for(i=1;i<=n;i++)
    {
        fin>>x;
        update(x,i);
    }
    for(i=1;i<=m;i++)
    {
        fin>>op;
        if(op==0)
        {
            fin>>a>>b;
            update(b,a);
        }
        if(op==1)
        {
            fin>>a>>b;
            fout<<sum(b)-sum(a-1)<<"\n";
        }
        if(op==2)
        {
            fin>>a;
            fout<<querry(a)<<"\n";
        }
    }
}