#include <fstream>
using namespace std;
const int NMAX = 100003;
int aib[NMAX], n;

void update(int poz, int nr)
{
    while (poz <= n)
    {
        aib[poz] += nr;
        poz += (poz & -poz);
    }
}

int query(int val)
{
    int ans = 0;
    while (val)
    {
        ans += aib[val];
        val -= (val & -val);
    }
    return ans;
}

int main()
{
    ifstream cin("aib.in");
    ofstream cout("aib.out");
    int i, m;
    cin >> n >> m;
    for (i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        update(i, x);
    }
    while (m--)
    {
        int op;
        cin >> op;
        if (op == 0)
        {
            int a, b;
            cin >> a >> b;
            update(a, b);
        }
        else if (op == 1)
        {
            int a, b;
            cin >> a >> b;
            cout << query(b) - query(a - 1) << "\n";
        }
        else
        {
            int a;
            cin >> a;
            int st = 1, dr = n, sol = -1;
            while (st <= dr)
            {
                int med = ((st + dr) >> 1);
                if (query(med) >= a)
                {
                    sol = med;
                    dr = med - 1;
                }
                else
                    st = med + 1;
            }
            cout << sol << "\n";
        }
    }
}