#include <stdio.h>

#define zeros(x) (x ^ (x - 1)) & x
#define NMAX 100001

long aib[NMAX], a, b, code, n, m;

void add(long a, long b)
{
	for (long i = a; i <= n; i += zeros(i))
		aib[i] += b;
}

long compute(long a)
{
	long tmp = 0;

	for (long i = a; i > 0; i -= zeros(i))
		tmp += aib[i];

	return tmp;
}

long bin_search(long left, long right, long x)
{
	long mid = (left + right) / 2, tmp = compute(mid);
	if (tmp == x)
		return mid;

	if (left == right)
		return -1;

	if (tmp > x)
	{
		return bin_search(left, mid - 1, x);
	}

	return bin_search(mid + 1, right, x);
}

int main()
{
	freopen ("aib.in", "rt", stdin);
	freopen ("aib.out", "wt", stdout);

	scanf("%ld %ld", &n, &m);
	for (long i = 1; i <= n; ++i)
	{
		scanf("%ld", &a);
		add(i, a);
	}

	for (long i = 0; i < m; ++i)
	{
		scanf("%ld %ld", &code, &a);
		if (code != 2)
			scanf("%ld", &b);

		if (code == 0)
		{
			add(a, b);
		}
		else
		if (code == 1)
		{
			printf("%ld\n", compute(b) - compute(a - 1));
		}
		else
		if (code == 2)
		{
			printf("%ld\n", bin_search(1, n, a));
		}
	}

	return 0;
}