#include <fstream>

using namespace std;

ifstream cin("aib.in");
ofstream cout("aib.out");
const int N = 100000;
long long aib[N + 1];

void update(int val, int pos)
{
    while(pos <= N)
    {
        aib[pos] += val;
        pos += (pos & (-pos));
    }
}
long long query(int a)
{
    long long s = 0;
    while(a > 0)
    {
        s += aib[a];
        a -= (a & (-a));
    }
    return s;
}

int main()
{
    int i, n, m, tip, a, b, x, st, dr, mij, rez, k;
    cin >> n >> m;
    for(i = 1; i <= n; i++)
    {
        cin >> x;
        update(x, i);
    }
    for(i = 0; i < m; i++)
    {
        cin >> tip;
        if(tip == 0)
        {
            cin >> a >> b;
            update(b, a);
        }
        else if(tip == 1)
        {
            cin >> a >> b;
            cout << query(b) - query(a - 1) << "\n";
        }
        else
        {
            cin >> k;
            st = 1;
            dr = n;
            while(st <= dr)
            {
                mij = (st + dr) / 2;
                if(query(mij) <= k)
                {
                    rez = mij;
                    st = mij + 1;
                }
                else
                {
                    dr = mij - 1;
                }
            }
            if(query(rez) == k)
                cout << rez << "\n";
            else
                cout << "-1\n";
        }
    }
    return 0;
}