#include <fstream>
#define NMAX 100001

using namespace std;

ifstream cin("aib.in");
ofstream cout("aib.out");

int n,m,i,j,k;

int BIT[NMAX];

void Update_T(int x,int y)
{
    while(y<=n)
    {
        BIT[y]+=x;
        y+=y&-y;
    }
}

int Query_T(int y)
{
    int rez=0;

    while(y>0)
    {
        rez+=BIT[y];
        y-=y&-y;
    }

    return rez;
}

int Min_Poz(int x)
{
    int y=0,z=1;

    while(z<n)
        z*=2;

    while(y+z<=n)
    {
        if(BIT[y+z]<=x)
        {
            y+=z;
            x-=BIT[y];

            if(!x)
                return y;
        }

        z/=2;
    }

    return -1;
}


int main()
{
    cin>>n>>m;

    for(int x=1;x<=n;++x)
    {
        cin>>i;
        Update_T(i,x);
    }

    while(cin>>k)
    {
        if(k==0)
        {
            cin>>j>>i;
            Update_T(i,j);
        }
        if(k==1)
        {
            cin>>i>>j;
            cout<<Query_T(j)-Query_T(i-1)<<'\n';
        }
        if(k==2)
        {
            cin>>i;
            cout<<Min_Poz(i)<<'\n';
        }
    }

    return 0;
}
/*
8 7
25 42 8 15 1 1 1 67
0 5 12
2 105
2 103
2 90
1 7 7
1 2 8
2 241
*/