#include <bits/stdc++.h>
#include <fstream>

using namespace std;

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

int N,M;
int aib[100001];

void update(int val, int x)
{
    do
    {
        aib[x]+=val;
        x+= x&(-x);
    }
    while(x<=N);
}
int Search(int);
int query(int x)
{
    int suma=0;
    while(x!=0)
    {
        suma+=aib[x];
        x-=x&(-x);
    }
    return suma;
}

int main()
{
    f>>N>>M;
    int x;
    for(int i=1; i<=N; ++i)
    {
        f>>x;
        update(x,i);
    }

    int tip,a ,b;
    for(int i=1; i<=M; ++i)
    {
        f>>tip;
        if(tip==1)
        {
            f>>a>>b;
            g<<query(b)-query(a-1)<<"\n";
        }
        else if(tip==0)
        {
            f>>a>>b;
            update(b,a);
        }
        else
        {
            f>>a;
            g<<Search(a)<<"\n";
        }
    }

    return 0;
}
int Search(int val)
{
    int i, step;
    for (step=1;step<N;step*=2);

    for(i=0;step!=0;step/=2)
    {
         if(i+step<=N)
         {
            if(val>=aib[i+step])
            {
                //cout<<i<<" ";
                i+=step;
                val-=aib[i];
                if ( !val ) return i;
            }
         }
    }
    return -1;
}