#include <bits/stdc++.h>
#define z(x) (x & (-x))

using namespace std;

int ARB[100100], n, m, x, a, b;

void add(int x, int val)
{
    for (; x < 100100; x += z(x) ) ARB[x] += val;
}

int get(int x)
{
    int s = 0;
    for (; x; x -= z(x)) s += ARB[x];
    return s;
}


int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ifstream cin("aib.in");
    ofstream cout("aib.out");
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> x, add(i, x);
	while (m--)
	{
	    cin >> x;
	    if (!x) cin >> a >> b, add(a, b);
	    else if (x == 1) cin >> a >> b, cout << get(b) - get(a - 1) << "\n";
	    else
	    {
	        cin >> a;
	        int st = 1, rs = -1, dr = 100000;
	        while (st <= dr)
	        {
	            int mid = (st + dr) / 2;
	            if (get(mid) == a) rs = mid;
	            if (get(mid) >= a) dr = mid - 1;
	            else st = mid + 1;
	        }
	        cout << rs << "\n";
	    }
	}
    cerr << "Fucking time elapsed: " << clock() * 1000.0 / CLOCKS_PER_SEC << " ms" << '\n';
    return 0;
}