#include <iostream>
#include <fstream>
#define zeros(x) ((x ^ (x - 1)) & x)
#define NMAX 100005
using namespace std;
ifstream f ("aib.in");
ofstream g ("aib.out");
int AIB[NMAX], n, m;
void update(int poz, int value)
{
    for (int i = poz; i <= n; i += zeros(i))
        AIB[i] += value;
}
int suma(int poz)
{
    int sum = 0;
    for (int i = poz; i >= 1; i -= zeros(i))
        sum += AIB[i];
    return sum;
}
int cautare(int value)
{
    int s = 1;
    for (; s < n; s <<= 1);
    for (int i = 0; s; s >>= 1)
    {
        if (i + s <= n)
        {
            if (value >= AIB[i + s])
            {
                i += s;
                value -= AIB[i];
                if (!value) return i;
            }
        }
    }
    return -1;
}

int main()
{
    f>>n>>m;
    for (int x, i = 1; i <= n; i++)
    {
        f>>x;
        update(i, x);
    }
    for (int p, x, y, i = 1; i <= m; i++)
    {
        f>>p >> x;
        if (p == 0)
        {
            f>>y;
            update(x, y);
        }
        else if (p == 1)
        {
            f >> y;
            g<<suma(y) - suma(x - 1)<<'\n';
        }
        else if (p == 2)
        {
            g<<cautare(x)<<'\n';
        }
    }
    return 0;
}