#include <bits/stdc++.h>
using namespace std;
int n, q, query, poz, value, poz1, poz2, suma, st, dr, mij, i, rezultat, suma_primilor_mij_termeni, aib[400005];
int LastBit(int x)
{
    return x & (-x);
}
void add(int poz, int val)
{
    for(int i = poz; i <= n; i = i + LastBit(i))
        aib[i] = aib[i] + val;
}
int sum(int poz)
{
    int rez = 0;
    for(int i = poz; i > 0; i = i - LastBit(i))
        rez = rez + aib[i];
    return rez;
}
int main()
{
    ifstream f("aib.in");
    ofstream g("aib.out");
    f >> n >> q;
    for(i = 1; i <= n; i ++)
    {
        f >> value;
        add(i, value);
    }
    for(i = 1; i <= q; i ++)
    {
        f >> query;
        if(query == 0)
        {
            f >> poz >> value;
            add(poz, value);
        }
        if(query == 1)
        {
            f >> poz1 >> poz2;
            int alfa = sum(poz2);
            int beta = sum(poz1 - 1);
            g << alfa - beta << "\n";
        }
        if(query == 2)
        {
            f >> suma;
            st = 1;
            dr = n;
            rezultat = -1;
            while(st <= dr)
            {
                mij = (st + dr) / 2;
                suma_primilor_mij_termeni = sum(mij);
                if(suma_primilor_mij_termeni == suma)rezultat = mij, dr = st - 1;
                else if(suma_primilor_mij_termeni > suma)dr = mij - 1;
                else st = mij + 1;
            }
            g << rezultat << "\n";
        }
    }
    return 0;
}