#include <bits/stdc++.h>
#define N_MAX 100005
#define lsb(i) ((i & (i - 1)) ^ i)

using namespace std;

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

int N, Q, bit[N_MAX];

void Update(int poz, int val)
{
    for (int i = poz; i <= N; i += lsb(i))
        bit[i] += val;
}

int Query(int poz)
{
    int ret = 0;
    for (int i = poz; i > 0; i -= lsb(i))
        ret += bit[i];
    return ret;
}

int GenMin(int val)
{
    int ret = 0, sum = 0;
    for (int i = 18; i >= 0; i--)
        if (ret + (1 << i) < N && sum + bit[ret + (1 << i)] < val)
        {
            ret += (1 << i);
            sum += bit[ret];
        }
    if (Query(ret + 1) != val)
        return -1;
    return ret + 1;
}

int main()
{
    fin >> N >> Q;
    for (int i = 1; i <= N; i++)
    {
        int x;
        fin >> x;
        Update(i, x);
    }

    while (Q--)
    {
        int op, a, b;
        fin >> op >> a;
        if (op == 0)
        {
            fin >> b;
            Update(a, b);
        }
        else if (op == 1)
        {
            fin >> b;
            fout << Query(b) - Query(a - 1) << "\n";
        }
        else
            fout << GenMin(a) << "\n";
    }
    return 0;
}