#include <iostream>
#include <fstream>
#define zeros(x) ((x^(x-1))&x)
#define N 100010

using namespace std;

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

int AIB[N],i,n,j,m,t,p,r,l,k;

void Add(int x,int quant)
{
    int i;
    for(i=x;i<=n;i+=zeros(i))
        AIB[i]+=quant;
}
int Query(int x)
{
    int i,sum=0;
    for(i=x;i>0;i-=zeros(i))
        sum=sum+AIB[i];
    return sum;
}
int caut(int val)
{
    int i,j;
    for(j=1;j<=n;j<<=1);

    for(i=0;j;j>>=1)
    {
        if(i+j<=n)
        {
            if(val>=AIB[i+j])
            {
                i+=j;
                val=val-AIB[i];
                if(val==0)
                    return i;
            }
        }
    }
    return -1;
}
int main()
{
    int x,y,z;
    f>>n>>m;
    for(i=1;i<=n;i++)
    {
        f>>x;
        Add(i,x);
    }
    while(m!=0)
    {
        f>>x;
        if(x==0)
        {
            f>>y>>z;
            Add(y,z);
        }
        else
            if(x==1)
            {
                f>>y>>z;
                g<<Query(z)-Query(y-1)<<"\n";
            }
            else
                if(x==2)
                {
                    f>>y;
                    g<<caut(y)<<"\n";
                }
        m--;
    }
}