#include <fstream>

using namespace std;

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

int N, M;
int AIB[100001];
int nr, type, a, b;

int lsb(int idx)
{
    return idx ^ (idx & (idx - 1));
}

void update(int idx, int val)
{
    while (idx <= N)
    {
        AIB[idx] += val;
        idx += lsb(idx);
    }
}

int compute(int idx)
{
    int sum = 0;
    while (idx > 0)
    {
        sum += AIB[idx];
        idx -= lsb(idx);
    }
    return sum;
}

int bs(int val)
{
    int l = 0, r = N + 1;

    while (r - l > 1)
    {
        int mid = (l + r ) / 2;
        int sum = compute(mid);

        if (AIB[mid] < val)
            l = mid;
        else
            r = mid;
    }

    if (compute(r) == val)
        return r;
    return -1;
}

int main()
{
    fin >> N >> M;
    for (int i = 1; i <= N; ++i)
    {
        fin >> nr;
        update(i, nr);
    }

    for (int i = 1; i <= M; ++i)
    {
        fin >> type;

        if (type == 0)
        {
            fin >> a >> b;
            update(a, b);
        }
        else if (type == 1)
        {
            fin >> a >> b;
            fout << compute(b) - compute(a - 1) << '\n';
        }
        else if (type == 2)
        {
            fin >> a;
            fout << bs(a) << '\n';
        }
    }

    fin.close();
    fout.close();
    return 0;
}