#include<iostream>
#include <fstream>
#include <algorithm>

using namespace std;

ifstream f("aib.in");
ofstream g("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;
    f >> n >> m;
    for(i = 1; i <= n; i ++)
    {
        f >> x;
        add(i, x);
    }
    for(i = 1; i <= m; i ++)
    {
        f >> c;
        if(c == 0)
        {
            f >> a >> b;
            add(a, b);
        }
        if(c == 1)
        {
            f >> a >> b;
            g << sum(b) - sum(a - 1) << "\n";
        }
        if(c == 2)
        {
            f >> 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)
                g << rez << "\n";
            else
                g << "-1\n";
        }
    }
    f.close();
    g.close();
    return 0;
}