#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 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: int i = 1, j = n, m;
                while (i <= j)
                    if (a < S(m = (i+j) >> 1))
                        j = m - 1;
                    else i = m + 1;
                out << (j and j <= n and S(j) == a? j: -1) << '\n';
        }
    }
}