#include <cstdio>
using namespace std;

#define NMAX 100001

int i, j, c, N, M;
int y, a, b;

int AIB[NMAX];

void update(int poz, int val) {
	for (int x = poz; x <= N; x += (x & -x)) AIB[x] += val;
}

int query(int i) {
	int result = 0;
	for (int x = i; x; x -= (x & -x)) result += AIB[x];
	return result;
}

int Binary_Search(int x) {
	int st = 1, dr = N, mid, cnt, ret;
	while (st <= dr) {
		mid = (st + dr) >> 1;
		cnt = query(mid);
		if (cnt == x)
			ret = mid, dr = mid - 1;
		else {
			if (cnt > x)
				dr = mid - 1;
			else
				st = mid + 1;
		}
	}
	return ret;
}

int main() {
	freopen("aib.in","r",stdin);
	freopen("aib.out","w",stdout);
	scanf("%i%i", &N, &M);
	for (i = 1; i <= N; ++i) {
		scanf("%i", &y);
		update(i, y);
	}
	for (i = 1; i <= M; ++i) {
		scanf("%i", &c);
		if (c == 0) {
			scanf("%i%i", &a, &b);
			update(a, b);
			continue;
		}
		if (c == 1) {
			scanf("%i%i", &a, &b);
			printf("%i\n", query(b) - query(a - 1));
			continue;
		}
		scanf("%i", &a);
		printf("%i\n", Binary_Search(a));
	}
	return 0;
}