#include <fstream>

using namespace std;

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

int c[100005], n, m, op;

void aduna(int pos, int val)
{
    int x, z;
    x = pos;
    do
    {
        c[x] += val;
        z = x & (x ^ (x - 1));
        x += z;
    }
    while(x <= n);
}

int suma(int pos)
{
    int x, z, s;
    s = 0;
    x = pos;

    do
    {
        s += c[x];
        z = x & (x ^ (x - 1));
        x -= z;
    }
    while(x >= 1);
    return s;
}

int cb(int k)
{
    int st = 1, dr = n;
    while(st <= dr)
    {
        int mid = (st + dr) / 2;
        int s = suma(mid);
        if(s < k)
            st = mid + 1;
        else if(s > k)
            dr = mid - 1;
        else if(s == k)
            return mid;
    }
    return -1;
}

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; ++i)
    {
        int a;
        cin >> a;
        aduna(i, a);
    }
    for(int i = 1; i <= m; ++i)
    {
        int op, pos, val, x, y, k;
        cin >> op;
        if(op == 0)
        {
            cin >> pos >> val;
            aduna(pos, val);
        }
        else if(op == 1)
        {
            cin >> x >> y;
            cout << suma(y) - suma(x - 1) << '\n';
        }
        else
        {
            cin >> k;
            cout << cb(k) << '\n';
        }
    }
    return 0;
}