#include <fstream>
#define fisier "aib"
std::ifstream in(fisier ".in");
std::ofstream out(fisier ".out");
int V[100001], n, m;
int S(int i)
{
    int s = 0;
    for (; i; i ^= i & -i)
        s += V[i];
    return s;
}

void U(int i, int e)
{
    for (; i <= n; i += i & -i)
        V[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';
        }
    }
}