#include <fstream>
#define VAL 100005

using namespace std;

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

int N, M, i, j;
int op, a, b, x;
int aib[VAL];

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

void update(int a, int b)
{
    while (a<=N)
    {
        aib[a]+=b;
        a+=zero(a);
    }
}

int suma(int a, int b)
{
    int x=0;
    int y=0;
    a--;
    while (a>0)
    {
        x+=aib[a];
        a-=zero(a);
    }
    while (b>0)
    {
        y+=aib[b];
        b-=zero(b);
    }
    return y-x;
}

int cautare(int a)
{
    int x=1;
    int nr=0;
    while (x<=N)
      x*=2;
    x/=2;
    while (x>0)
    {
        if (a>=aib[nr+x])
        {
            a-=aib[nr+x];
            nr+=x;
            if (a==0)
              return nr;
        }
        x/=2;
    }
    return -1;
}

int main()
{
    fin >> N >> M;
    for (i=1; i<=N; i++)
    {
        fin >> x;
        update(i, x);
    }
    for (i=1; i<=M; i++)
    {
        fin >> op;
        if (op==0)
        {
            fin >> a >> b;
            update(a, b);
        }
        if (op==1)
        {
            fin >> a >> b;
            fout << suma(a, b) << '\n';
        }
        if (op==2)
        {
            fin >> a;
            fout << cautare(a) << '\n';
        }
    }
    fin.close();
    fout.close();
    return 0;
}