#include <fstream>

using namespace std;

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

int AIB[100001], v[100001], n, m;

inline int zeros(int x)
{
    return x & (-x);
}

inline void add(int c, int poz)
{
    for (int i = poz; i <= n; i += zeros(i))
        AIB[i] += c;
}

inline int compute(int poz)
{
    int rez = 0;
    for (int i = poz; i > 0; i -= zeros(i))
        rez += AIB[i];
    return rez;
}

inline int sum(int x)
{
    int i, lg;
    for (lg = 1; lg <= n; lg <<= 1);
    for (i = 1; lg; lg >>= 1)
    {
        if (i + lg <= n && compute(i + lg) <= x)
            i += lg;
    }
    if (compute(i) != x)
        return -1;
    return i;
}

int main()
{
    int c, a, b;
    in >> n >> m;
    for (int i = 1; i <= n; ++i)
    {
        in >> v[i];
        add(v[i], i);
    }
    for (int q = 1; q <= m; ++q)
    {
        in >> c;
        if (c == 0)
        {
            in >> a >> b;
            v[a] += b;
            add(b, a);
        }
        else if (c == 1)
        {
            in >> a >> b;
            out << compute(b) - compute(a - 1) << '\n';
        }
        else
        {
            in >> a;
            out << sum(a) << '\n';
        }
    }
    return 0;
}