#include <cstdio>
#include <cstring>
#include <algorithm>

#include <vector>
#include <set>
#include <map>


using namespace std;

unsigned int A[1<<18];

unsigned int N, M;

void updateNode(unsigned int val, unsigned int pos) {
	unsigned int real_pos = (1 << 17) + pos;
	
	A[real_pos] += val;
	
	while (real_pos > 1) {
		real_pos = real_pos >> 1 ; 
		A[real_pos] += val;
	}
}

unsigned int get_element(unsigned int pos) {
	int real_pos = (1 << 17) + pos;
	return A[real_pos];
}

unsigned int get_sum(unsigned int pos) {
	int virt = 1 << 17, current = 1;
	unsigned int sum = 0;
	
	while (virt) {
		current <<= 1;
		virt >>= 1;
		if (virt & pos ) {
			current ++;
			sum += A[current - 1];	
		}
		
	}
	
	return sum;
}

unsigned int get_pos(unsigned int sum) {
	int current = 2;
	if (!sum)
		return 0;
	
	for (; current < (1 << 18); current = current << 1) {
		
		if (A[current] < sum) {
			sum -= A[current];
			current++;
		}

	}

	current >>= 1;
	
	if (sum != A[current])
		return -1;
	else
		return current - (1 << 17);
}

int main () {
	unsigned int val, type, a , b;
	freopen("aib.in", "r", stdin);
	freopen("aib.out", "w", stdout);
	
	scanf("%u %u", &N, &M);
	
	for (unsigned int i = 0; i < N ; i++) {
		scanf("%u", &val);
		updateNode(val, i);
	}
	
	for (unsigned int i = 0; i < M; i++) {
		scanf("%u", &type);
		switch(type) {
		case 0:
			scanf("%u %u", &a, &b);
			updateNode(b, a - 1);
			break;
		case 1:
			scanf("%u %u", &a, &b);
			printf("%u\n", get_sum(b - 1) - get_sum(a - 1) + get_element(b - 1));
			break;
		case 2:
			scanf("%u", &a);
			printf("%u\n", get_pos(a) + (unsigned int)1);
			break;
		default:
			break;
		}
	}
	
	return 0;
}