#include <fstream>

using namespace std;

ifstream cin("aib.in");
ofstream cout("aib.out");

int aib[100005];

int n;

int len(int x)
{
    return x - (x & (x - 1));
}

int q(int pz)
{
    int sum = 0;
    while(pz > 0)
    {
        sum += aib[pz];
        pz -= len(pz);
    }
    return sum;
}

void u(int pz , int val)
{
    while(pz <= n)
    {
        aib[pz] += val;
        pz += len(pz);
    }
}

int main()
{
    int k , ac , i , p , a , b , pas , val;
    cin >> n >> k;
    for(i = 1; i <= n; i++)
    {
        cin >> val;
        u(i , val);
    }
    for(i = 1; i <= k; i++)
    {
        cin >> p;
        if(p == 0)
        {
            cin >> a >> b;
            u(a , b);
        }
        else
        if(p == 1)
        {
            cin >> a >> b;
            cout << q(b) - q(a - 1) << '\n';
        }
        else
        if(p == 2)
        {
            cin >> a;
            if(a == 0)
                cout << -1 << '\n';
            else
            {
            ac = 0;
            pas = 1 << 20;
            while(pas)
            {
                if(ac + pas <= n)
                if(a >= aib[ac+pas])
                    ac += pas , a -= aib[ac];
                pas >>= 1;
            }
            if(!a)
            cout << ac << '\n';
            else
            cout << "-1" << '\n';
            }
        }
    }

    return 0;
}