#include <fstream>
#include <algorithm>

using namespace std;

ifstream fin("aib.in");
ofstream fout("aib.out");

const int NMAX = 100000;
int AIB[NMAX + 5];
int n;

int zeros(int x)
{
    return (x ^ (x - 1)) & x;
}

void add(int x, int val)
{
    int i;
    for(i = x; i <= n; i += zeros(i))
        AIB[i] += val;
}

int sum(int inde1)
{
    int i, s;
    s = 0;
    for(i = inde1; i > 0; i -= zeros(i))
        s += AIB[i];
    return s;
}

int main()
{
    int m, x, i, c, a, b, st, dr, mij, rez;
    fin >> n >> m;
    for(i = 1; i <= n; i ++)
    {
        fin >> x;
        add(i, x);
    }
    for(i = 1; i <= m; i ++)
    {
        fin >> c;
        if(c == 0)
        {
            fin >> a >> b;
            add(a, b);
        }
        if(c == 1)
        {
            fin >> a >> b;
            fout << sum(b) - sum(a - 1) << "\n";
        }
        if(c == 2)
        {
            fin >> a;
            st = 1;
            dr = n;
            while(st <= dr)
            {
                mij = (st + dr) / 2;
                if(sum(mij) <= a)
                {
                    rez = mij;
                    st = mij + 1;
                }
                else
                    dr = mij - 1;
            }
            if(sum(rez) == a)
                fout << rez << "\n";
            else
                fout << "-1\n";
        }
    }
    return 0;
}