#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
ifstream f("aib.in");
ofstream g("aib.out");
int c, a, b, n, m, aib[N];
void upd(int p, int val)
{
    for(; p <= n; p+=p&(-p))
        aib[p]+=val;
}
inline int suma(int p)
{
    int ret = 0;
    for(; p; p -= p&(-p))
        ret += aib[p];
    return ret;
}
int main()
{
    f >> n >> m;
    for(int i = 1; i <= n; i++)
    {
        f >> c;
        upd(i, c);
    }
    for(; m; m--)
    {
        f >> c >> a;
        if(c == 0)
            f >> b, upd(a, b);
        else if(c == 1)
            f >> b, g << suma(b) - suma(a - 1) << '\n';
        else
        {
            int st = 0, hi = n, mi;
            while(hi - st > 1)
            {
                mi = (st + hi) / 2;
                if(suma(mi) >= a)
                    hi = mi;
                else
                    st = mi;
            }
            if(suma(hi) != a)
                hi = -1;
            g << hi << '\n';
        }
    }
    return 0;
}