/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

#include <iostream>
#include <fstream>
#define Max 100005
using namespace std;

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

int arb[4*Max],n,m;

void update(int val, int pos, int st, int dr, int nod);
void query (int a, int b, int st, int dr, int nod,int &sum);

int main()
{
    fin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        int x;
        fin>>x;
        update(x,i,1,n,1);
    }
    for(int i=1;i<=m;i++)
    {
        int c,a,b;
        fin>>c;
        if(c==0)
        {
            fin>>a>>b;
            update(b,a,1,n,1);
        }
        if(c==1)
        {
            fin>>a>>b;
            int sum=0;
            query(a,b,1,n,1,sum);
            fout<<sum<<"\n";
        }
        if(c==2)
        {
            fin>>a;
            int ok=0;
            int in=1,fin=n;
            while(in<=fin)
            {
                int mij=(in+fin)/2;
                int sum=0;
                query(1,mij,1,n,1,sum);
                if(sum==a)
                {
                    fout<<mij<<"\n";
                    ok=1;
                    break;
                }
                if(sum<a)
                    in=mij+1;
                else if(sum>a)
                    fin=mij-1;
            }
            if(ok==0)
            fout<<"-1"<<"\n";
        }
    }

    return 0;
}

void update(int val, int pos, int st, int dr, int nod)
{
    if(st==dr)
    {
        arb[nod]+=val;
        return;
    }
    int mij=(st+dr)/2;
    if(pos<=mij)
        update(val,pos,st,mij,2*nod);
    else
        update(val,pos,mij+1,dr,2*nod+1);
    arb[nod]=arb[2*nod]+arb[nod*2+1];
}

void query (int a, int b, int st, int dr, int nod,int &sum)
{
    if(a<=st && dr<=b)
    {
        sum+=arb[nod];
        return;
    }
    int mij=(st+dr)/2;
    if(a<=mij)
        query(a,b,st,mij,2*nod,sum);
    if(mij<b)
        query(a,b,mij+1,dr,2*nod+1,sum);
}