#include <iostream>
#include <fstream>
#define MMAX 100002

using namespace std;

int n,m,aib[MMAX];

ifstream f("aib.in");
ofstream o("aib.out");

int next(int pos)
{
    return pos & (-pos);
}

void update(int pos, int val)
{
    while(pos <= n)
    {
        aib[pos] += val;
        pos += next(pos);
    }
}

int get_val(int pos)
{
    int sum = 0;
    while(pos > 0)
    {
        sum += aib[pos];
        pos -= next(pos);
    }
    return sum;
}

int main()
{
    int a,b;
    f >> n >> m;
    for(int i = 1; i <= n; ++i)
    {
        int val;
        f >> val;
        update(i,val);
    }

    for(int i = 1; i <= m; ++i)
    {
        int c;
        f >> c >> a;
        if(c == 0)
        {
            f >> b;
            update(a,b);
        }
        else if(c == 1)
        {
            f >> b;
            o << get_val(b) - get_val(a-1) << '\n';
        }
        else
        {
            int st = 1, dr = n, pos = -1, mij, aux;
            while(st <= dr)
            {
                mij = st + (dr - st) / 2;
                aux = get_val(mij);
                if(aux <= a)
                {
                    if(aux == a)
                    {
                        pos = mij;
                    }
                    st = mij + 1;
                }
                else
                    dr = mij - 1;
            }

            o << pos << '\n';
        }
    }
    return 0;
}