#include <iostream>
#include <fstream>
#define lsb(x) ((-x)&x)
using namespace std;
ifstream f("aib.in");
ofstream g("aib.out");
int arb[100005],n,m;
inline void actualizare(int valoare,int pozitie)
{
    for(int ii=pozitie; ii<=n; ii+=lsb(ii))
    {
        arb[ii]+=valoare;
    }
}
inline int calculez(int pozitie)
{
    int suma=0;
    for(int ii=pozitie; ii>0; ii-=lsb(ii))
        suma+=arb[ii];
    return suma;
}
inline int dif(int poz1,int poz2)
{
    return (calculez(poz2)-calculez(poz1-1));
}
inline int instr2(int val)
{
    int st=1,dr=n,mij,poz=-1;
    while(st<=dr)
    {
        mij=(st+dr)/2;
        if(calculez(mij)==val)
        {
            return mij;
        }
        else if(calculez(mij)>mij)
        {
            dr=mij-1;
        }
        else st=mij+1;
    }
    return -1;
}
int main()
{
    f>>n>>m;
    for(int i=1; i<=n; i++)
    {
        int val;
        f>>val;
        actualizare(val,i);
    }
    for(int i=1; i<=m; i++)
    {
        int instr;
        f>>instr;
        if(instr==0)
        {
            int a,b;
            f>>a>>b;
            actualizare(b,a);
        }
        else if(instr==1)
        {
            int a,b;
            f>>a>>b;
            g<<dif(a,b)<<endl;
        }
        else
        {
            int a;
            f>>a;
            g<<instr2(a)<<endl;
        }
    }
    return 0;
}