#include<iostream>
#include<fstream>
#define DX 100010
using namespace std;
fstream fin("aib.in",ios::in),fout("aib.out",ios::out);
int aib[DX],n,m;
int isb(int x)
{
    return ((x&(x-1))^x);
}
void update(int x,int b)
{
    for( ;x<=n;x+=isb(x)) aib[x]+=b;
}
int scuipatot(int x)
{
    int s=0;
    for( ;x>0;x-=isb(x)) s+=aib[x];
    return s;
}
int cauta(int sum)
{
    int poz,i=0;
    for(poz=1;poz<n;(poz<<=1));
    while(poz!=0)
    {
        if(i+poz<=n && sum>=aib[i+poz])
        {
            i+=poz;
            sum-=aib[i];
            if(sum==0) return i;
        }
        (poz>>=1);
    }
    return -1;
}
int main()
{
    int i,j,t,a,b;
    fin>>n>>m;
    for(i=1;i<=n;i++)
    {
        fin>>a;
        update(i,a);
    }
    for(i=1;i<=m;i++)
    {
        fin>>t;
        if(t==0)
        {
            fin>>a>>b;
            update(a,b);
        }
        if(t==1)
        {
            fin>>a>>b;
            fout<<scuipatot(b)-scuipatot(a-1)<<"\n";
        }
        if(t==2)
        {
            fin>>a;
            fout<<cauta(a)<<"\n";
        }
    }
}