#include <bits/stdc++.h>
using namespace std;
ifstream f("aib.in");
ofstream g("aib.out");
int n, q, v[100009];
int sum(int x)
{
    int rez = 0;
    while (x > 0)
        rez += v[x], x -= x & -x;
    return rez;
}
int main()
{
    f >> n >> q;
    for (int i = 1, x; i <= n; i++)
    {
        f >> x;
        v[i] += x;
        if (i + (i & -i) <= n)
            v[i + (i & -i)] += v[i];
    }
    for (int a, b, c; q; q--)
    {
        f >> c;
        if (!c)
        {
            f >> a >> b;
            while (a <= n)
                v[a] += b, a += a & -a;
        }
        else if (c == 1)
        {
            f >> a >> b;
            g << sum(b) - sum(a - 1) << '\n';
        }
        else
        {
            f >> a;
            int st = 1, dr = n, p = -1;
            while (st <= dr)
            {
                int mid = (st + dr) / 2;
                int r = sum(mid);
                if (r == a)
                    p = mid, dr = mid - 1;
                else if (r < a)
                    st = mid + 1;
                else
                    dr = mid - 1;
            }
            g << p << '\n';
        }
    }
    return 0;
}