#include <iostream>
#include <fstream>
#include <assert.h>

const char IN[] = "aib.in", OUT[] = "aib.out";
const int NMAX = 100001;

using namespace std;

int T[NMAX];
int N, M;

void set(int idx, int val) {
	while (idx <= N) {
		T[idx] += val;
		idx += (idx & (-idx));
	}
}

int get(int idx) {
	int s = 0;
	while (idx > 0) {
		s += T[idx];
		idx -= (idx & (-idx));
	}
	return s;
}

int get_sum(int a, int b) {
	return get(b) - get(a-1);
}

int get_k(int a) {
	int low = 1, high = N;
	while (low <= high) {
		int m = low + (high - low) / 2;
		int s = get(m);
		if (s == a) return m;
		if (s > a) high = m - 1;
		else low = m + 1;
	}
	return -1;
}

inline void read_data() {
	assert(freopen(IN, "r", stdin));
	assert(scanf("%d %d", &N, &M));
	for(int i = 1; i <= N; ++i) {
		int x;
		assert(scanf("%d", &x));
		set(i, x);
	}
	assert(freopen(OUT, "w", stdout));
	for (int i = 0; i < M; ++i) {
		int cod, a, b;
		assert(scanf("%d", &cod));
		switch (cod) {
		case 0: 
			assert(scanf("%d %d", &a, &b));
			set(a, b);
			break;
		case 1:
			assert(scanf("%d %d", &a, &b));
			printf("%d\n", get_sum(a, b));
			break;
		case 2:
			assert(scanf("%d", &a));
			printf("%d\n", get_k(a));
			break; 
		}
	}
	fclose(stdin);
	fclose(stdout);
}

int main() {
	read_data();
	return 0;
}