#include <bits/stdc++.h>

using namespace std;

inline void debug()
{
	freopen("aib.in", "r", stdin);
	freopen("aib.out", "w", stdout);
	ios::sync_with_stdio(NULL);
	cin.tie(0);cout.tie(0);
}

const int NMax = 1e5 + 10;
int arr[NMax], BIT[NMax], n, m, N;

int getParent(int index)
{
	return index - (index & -index);
}

int getNext(int index)
{
	return index + (index & -index);
}

void updateBIT(int val, int index)
{
	while(index <= N) {
		BIT[index] += val;
		index = getNext(index);
	}
}

void createBIT()
{
	for(int i = 1; i <= N; ++i)
		updateBIT(arr[i], i);
}

int getSum(int index)
{
	int sum = 0;

	while(index > 0) {
		sum += BIT[index];
		index = getParent(index);
	}

	return sum;
}

void findSum(int sum)
{
	int index = 1;
	while(index <= N) {
		if(BIT[index] == sum) {
			printf("%d\n", index);
			return;
		}
		index = getNext(index);
	}
	printf("%d\n", -1);
}

int main()
{
	debug();

	scanf("%d %d", &n, &m);

	for(int i = 1; i <= n; ++i)
		scanf("%d", &arr[i]);

	N = n + 1;

	createBIT();

	for(int i = 1; i <= m; ++i) {
		int op, a, b;
		scanf("%d", &op);

		if(op == 0) {
			scanf("%d %d", &a, &b);
			updateBIT(b, a);
		} else {
			if(op == 1) {
				scanf("%d %d", &a, &b);
				printf("%d\n", getSum(b) - getSum(a - 1));
			}
			else {
				scanf("%d", &a);
				findSum(a);
			}
		}
	}

	return 0;
}