#include <fstream>

using namespace std;

int aib[100005], n, m;

void Update (int p, int x)
{
    for (; p <= n; p += (p & - p))
        aib[p] += x;
}

int Query (int p)
{
    int s;
    for (s = 0; p > 0; p -= (p & - p))
        s += aib[p];
    return s;
}

int BinSearch (int k)
{
    int left, right, mid, pos = -1;
    left = 1;
    right = n;
    while (left <= right)
    {
        mid = (left + right) / 2;
        int x = Query(mid);
        if (x == k)
        {
            pos = mid;
            right = mid - 1;
        }
        else if (x < k)
            left = mid + 1;
        else right = mid - 1;
    }
    return pos;
}

void Solve ()
{
    ifstream fin ("aib.in");
    ofstream fout ("aib.out");
    int i, x, y, op;
    fin >> n >> m;
    for (i = 1; i <= n; i++)
    {
        fin >> x;
        Update(i, x);
    }
    for (i = 1; i <= m; i++)
    {
        fin >> op;
        if (!op)
        {
            fin >> x >> y;
            Update(x, y);
        }
        else if (op == 1)
        {
            fin >> x >> y;
            fout << Query(y) - Query(x - 1) << "\n";
        }
        else
        {
            fin >> x;
            fout << BinSearch(x) << "\n";
        }
    }
}

int main()
{
    Solve();
    return 0;
}