//HighFlow
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <fstream>
#include <string.h>
#include <math.h>
#include <algorithm>
#define fcat(c) while (c!='\n') fscanf(f,"%c",&c)
#define cat(c) while (c!='\n') scanf("%c",&c)
#define For(i,st,dr,k) for (int i=st;i<=dr;i+=k)
#define ll (long long)
using namespace std;
FILE *f,*g;
int t[100100];
int n,m,a,b,x,i,tp;

void update(int x, int ind)
{
    for (;ind<=n;ind+=(ind &(-ind)))
    {
        t[ind]+=x;
    }
}

inline int query1(int x, int y )
{
    int s1,s2;
    s1=s2=0;
    for (;x>0;x-=(x&(-x))) s1+=t[x];
    for (;y>0;y-=(y&(-y))) s2+=t[y];
    return s2-s1;
}

int Search(int val)
{
    int i, step;

    for ( step = 1; step < n; step <<= 1 );

    for( i = 0; step; step >>= 1 )
    {
         if( i + step <= n)
         {
            if( val >= t[i+step] )
            {
                i += step, val -=t[i];
                if ( !val ) return i;
            }
         }
    }

    return -1;
}

int main()
{
    f=fopen("aib.in","r");
    g=fopen("aib.out","w");

    fscanf(f,"%d%d",&n,&m);

    for (i=1;i<=n;i++)
    {
        fscanf(f,"%d",&x);
        update(x,i);
    }

    for (i=1;i<=m;i++)
    {
        fscanf(f,"%d",&tp);
        switch (tp)
        {
            case 0: fscanf(f,"%d%d",&a,&b); update(b,a); break;
            case 1: fscanf(f,"%d%d",&a,&b); fprintf(g,"%d\n",query1(a-1,b)); break;
            case 2: fscanf(f,"%d",&a); fprintf(g,"%d\n",Search(a));break;
        }
    }

	return 0;
}