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

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


using namespace std;

long long A=[1<<15];

long long N, M;

void updateNode(long long val, long long pos) {
	long long real_pos = (1 << 14) + pos;
	
	A[real_pos] += val;
	
	while (real_pos != 1) {
		real_pos >>= 1; 
		A[real_pos] += val;
	}
}

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

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

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

	}

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

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