#include <bits/stdc++.h>

using namespace std;

ifstream fin("aib.in");
ofstream fout("aib.out");
int n, m, op, x, y;
int a[100005];
struct vrajeala
{
    vector <int> aib;

    void Init(int d)
    {
        aib.resize(d);
    }

    void Update(int x, int y)
    {
        while (x <= n)
        {
            aib[x] += y;
            x += (x & (-x));
        }
    }
    int Query(int poz)
    {
        int s = 0;
        while (poz >= 1)
        {
            s += aib[poz];
            poz -= (poz & (-poz));
        }
        return s;
    }
    int CautBin(int k)
    {
        int st, dr, mij, x;
        st = 1;
        dr = n;
        while (st <= dr)
        {
            mij = (st + dr) / 2;
            x = Query(mij);
            if (x == k)
                return mij;
            if (x < k)
                st = mij + 1;
            else dr = mij - 1;
        }
        return -1;
    }
};
vrajeala tree;
int main()
{
    int i, j;
    fin >> n >> m;

    tree.Init(100005);

    for (i = 1; i <= n; i++)
    {
        fin >> a[i];
        tree.Update(i, a[i]);
    }

    while (m--)
    {
        fin >> op;
        if (op == 0)
        {
            fin >> x >> y;
            tree.Update(x, y);
        }
        else if (op == 1)
        {
            fin >> x >> y;
            fout << tree.Query(y) - tree.Query(x - 1) << "\n";
        }
        else
        {
            fin >> x;
            fout << tree.CautBin(x) << "\n";
        }
    }
    

    return 0;
}