#include <iostream>
#include <fstream>

using namespace std;

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

int aib[100005], n, q;

void Update(int p, int val) // adauga valoarea val la pozitia p
{
    for (; p <= n; p += (p & -p))
        aib[p] += val;
}

int Sum(int pos) // calculeaza suma de la pozitia 1 la pozitia pos in O(log n)
{
    int s;
    for (s = 0; pos > 0; pos -= (pos & -pos))
        s += aib[pos];
    return s;
}

int Query2(int val)
{
    int st = 1, dr = n, mij, poz = -1;
    while (st <= dr)
    {
        mij = (st + dr) / 2;
        int x = Sum(mij);
        if (x == val)
        {
            poz = mij;
            dr = mij - 1;
        }
        else if (x > val) dr = mij - 1;
        else st = mij + 1;
    }
    return poz;
}

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 != 2) fin >> b;
        if (op == 0)
            Update(a, b);
        else if (op == 1)
            fout << Sum(b) - Sum(a - 1) << "\n";
        else fout << Query2(a) << "\n";
    }
    return 0;
}