#include <bits/stdc++.h>
using namespace std;

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

int n,m,aint[400001];

void update(int poz,int in,int sf,int nod, int val)
{
    if(in==sf)
    {
        aint[nod]+=val;
        return;
    }
    int mij=(in+sf)/2;
    if(poz<=mij) update(poz, in, mij,nod*2,val);
    else update(poz, mij+1, sf, nod*2+1,val);
    aint[nod]=aint[2*nod]+aint[2*nod+1];
}

int cauta(int in,int sf,int a,int b,int nod)
{
    if(in==a && sf==b)
    {
        return aint[nod];
    }
    int mij=(in+sf)/2;
    if(mij>=b)
        return cauta(in, mij,a,b,2*nod);
    else if(mij<a)
        return cauta(mij+1, sf, a,b,2*nod+1);
    else
        return cauta(in, mij,a,mij,2*nod)+cauta(mij+1, sf, mij+1,b,2*nod+1);
}

int cauta2(int in,int sf,int nod,int s)
{
    if(in==sf && s==aint[nod]) return sf;
    else if(in==sf) return -1;

    int mij=(in+sf)/2;
    if(aint[2 * nod] < s) return cauta2(mij+1, sf, nod*2+1,s-aint[2 * nod]);
    return cauta2(in,mij,nod*2,s);

}

int main()
{
    fin>>n>>m;
    for(int i=1; i<=n; i++)
    {
        int elem;
        fin>>elem;
        update(i,1,n,1,elem);
    }
    for(int i=0; i<m; i++)
    {
        int a,b,task;
        fin>>task;
        if(task==0)
        {
            fin>>a>>b;
            update(a,1,n,1,b);
        }
        if(task==1)
        {
            fin>>a>>b;
            fout<<cauta(1,n,a,b,1)<<"\n";
        }
        if(task==2)
        {
            fin >> a;
            fout<<cauta2(1,n,1,a);
            fout<<"\n";
        }
    }
    return 0;
}