#include <fstream>
#define fisier "aib"
std::ifstream in(fisier ".in");
std::ofstream out(fisier ".out");
int V[100001], n, m;
constexpr 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 = 1, j = n, m;
    while (i <= j)
        if (s < S(m = (i+j)>>1))
            j = m - 1;
        else i = m + 1;
    return j and j <= n and S(j) == s? j: -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) << '\n';
        }
    }
}