#include <fstream>

using namespace std;
using ll=long long;

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

const int N=15e4+2;

ll cer,q,a,b,k,x,i,j;
ll aib[N],n;

void update(int poz,int val)
{
    while(poz<=n)
    {
        aib[poz]+=val;
        poz+=(poz&-poz);
    }
}
ll query(int poz)
{
    ll sum=0;
    while(poz)
    {
        sum+=aib[poz];
        poz-=(poz&-poz);
    }
    return sum;
}

int cb(int k)
{
    ll st=1,dr=n;
    while(st<=dr)
    {
        ll mij=(st+dr)/2;
        ll ans=query(mij);
        if(ans==k)
            return mij;
        if(ans>k)
            dr=mij-1;
        if(ans<k)
            st=mij+1;
    }
    return -1;
}

int main()
{
    fin>>n>>q;
    for(i=1; i<=n; i++)
    {
        fin>>x;
        update(i,x);
    }
    for(i=1; i<=q; i++)
    {
        fin>>cer;
        switch(cer)
        {
            case 0: fin>>a>>b; update(a,b); break;
            case 1: fin>>a>>b; fout<<query(b)-query(a-1)<<'\n'; break;
            case 2: fin>>k; fout<<cb(k)<<'\n'; break;
        }
    }
    return 0;
}