#include <fstream>
#include <vector>
using namespace std;
ifstream fin("aib.in");
ofstream fout("aib.out");
int n, i, j, a, b, m, op;
vector <int> aib;
void update (int val, int pos)
{
    for (int i = pos; i <= n; i += i & (-i))
        aib[i] += val;
}
int query (int a)
{
    int suma = 0; 
    for (int i = a; i > 0; i -= i & (-i))
        suma += aib[i];
    return suma;
}
int search (int a)
{
    int pos = 1, cp = 0;
    while (pos < n)
        pos *= 2;
    for (; pos > 0; pos/=2)
    {
        if (cp+pos <= n && a >= aib[cp+pos])
        {
            cp += pos; a -= aib[cp];
            if (a == 0) return cp;
        }
    }
    return -1;
}
int main()
{
    fin >> n >> m; aib.resize(n+1);
    for (i = 1; i <= n; i++)
    {
        fin >> a;
        update(a, i);
    }
    for (i = 1; i <= m; i++)
    {
        fin >> op;
        switch (op)
        {
            case 0:
            fin >> a >> b;
            update (b, a);
            break;
            case 1:
            fin >> a >> b;
            fout << query (b) - query(a-1) << '\n';
            break;
            case 2:
            fin >> a;
            fout << search(a) << '\n';
        }
    }
    return 0;
}