#include <fstream>

using namespace std;

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

int n, m;
int aib[100005];

int lsb(int x)  {
    return (x & (-x));
}

void Update(int nod, int val)    { //nodul si valoarea pe care o adaug
    while (nod <= n) {
        aib[nod] += val;
        nod += lsb(nod);
    }
}

int Query(int nod)  {
    int ans = 0;
    while (nod > 0) {
        ans += aib[nod];
        nod -= lsb(nod);
    }
    return ans;
}

int main()  {
    cin >> n >> m;
    int type, x, y;
    for (int i = 1; i <= n; ++i)    {
        cin >> x;
        Update(i, x);
    }
    while (m--) {
        cin >> type;
        if (type == 0)  {
            cin >> x >> y;
            Update(x, y);
        }
        if (type == 1)  {
            cin >> x >> y;
            cout << Query(y) - Query(x - 1) << '\n';
        }
        if (type == 2)  {
            cin >> x;
            int st = 1, dr = n, mij, ans = -1;
            while (st <= dr)    {
                mij = (st + dr) / 2;
                int aux = Query(mij);
                if (aux < x)  {
                    st = mij + 1;
                } else if (aux > x) {
                    dr = mij - 1;
                } else    {
                    ans = mij;
                    break;
                }
            }
            cout << ans << '\n';
        }
    }
    return 0;
}