#include<fstream>
using namespace std;

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

const int NMAX=100005;

int n,m,AIB[NMAX];

inline int zeros(int x)
{
    return x&(x^(x-1));
}

inline void Update(int x,int val)
{
    for (int i=x;i<=n;i+=zeros(i))
        AIB[i]+=val;
}

inline void Citire()
{
    int i,p;
    fin>>n>>m;
    for (i=1;i<=n;i++)
        {
            fin>>p;
            Update(i,p);
        }
}

inline int Compute(int x)
{
    int i,rez=0;
    for (i=x;i>0;i-=zeros(i))
        rez+=AIB[i];
    return rez;
}

inline void CautaPatrascu(int x)
{
    int minim=0,smen=1,aux=x;
    while (smen<=n) smen<<=1;
    smen>>=1;
    while (smen>=1)
        {
            if (AIB[minim+smen]<x)
            {x-=AIB[minim+smen];minim+=smen;}
            smen>>=1;
        }
    if (AIB[minim+1]!=aux) fout<<"-1";
    else fout<<minim+1;
    fout<<"\n";
}

inline void SOLVE()
{
    int i,x,y,z;
    for (i=1;i<=m;i++)
        {
            fin>>x>>y;
            if (!x) {fin>>z;Update(y,z);}
            if (x==1) {fin>>z;fout<<Compute(z)-Compute(y-1)<<"\n";}
            if (x==2) CautaPatrascu(y);
        }
}

int main()
{
    Citire();
    SOLVE();
    return 0;
}