#include <iostream>
#include <fstream>

using namespace std;

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

int v[111111],n;

void update(int ind, int val)
{
    while(ind<=n)
    {
        v[ind]+=val;
        ind=ind+(((ind^(ind-1))+1)>>1);
    }
}

int querry(int ind)
{
    int rez=0;
    while(ind!=0)
    {
        rez+=v[ind];
        ind=ind-(((ind^(ind-1))+1)>>1);
    }
    return rez;
}

int cauta(int k)
{
    int i,pas=1<<16;
    for(i=0;pas;pas/=2)
    {
        if(i+pas<=n && querry(i+pas)<k)
        {
            i+=pas;
        }
    }
    if(querry(i+1)==k)
        return i+1;
    return -1;
}


int main()
{
    int m,x,i,c,ind,val,a,b,k;
    in>>n>>m;
    for(i=1;i<=n;++i)
    {
        in>>x;
        update(i,x);
    }
    for(i=1;i<=m;++i)
    {
        in>>c;
        if(c==0)
        {
            in>>ind>>val;
            update(ind,val);
            continue;
        }
        if(c==1)
        {
            in>>a>>b;
            out<<querry(b)-querry(a-1)<<"\n";
            continue;
        }
        if(c==2)
        {
            in>>k;
            out<<cauta(k)<<"\n";
        }
    }
    return 0;
}