#include <fstream>
#define fisier "aib"
std::ifstream in(fisier ".in");
std::ofstream out(fisier ".out");
int V[100001], n, m;
int S(int i)               {return i? V[i] + S(i ^ i & -i): 0;}
void U(int i, int e)       {if (i <= n) V[i] += e, U(i + (i & -i), e);}
int P(int s, int i, int l) {return l? (s < S(i + (l >>= 1))? P(s, i, l): P(s, i + l, l)): (i and i <= n and S(i) == s? i: -1);}
int main()
{
    in >> n >> m;
    for (int i = 1; i <= n; i++)
        {int e; in >> e; U(i, e);}
    while (m--)
    {
        int v, a, b; in >> v >> a; if (v < 2) in >> b;
        switch (v)
        {
            case 0: U(a, b); break;
            case 1: out << S(b) - S(a-1) << '\n'; break;
            case 2: out << P(a, 1, n) << '\n';
        }
    }
}