#include <stdio.h>
#include <stdlib.h>


void update(int *v, int size, int index, int value);
int query(int *v, int size, int index);
int find(int *v, int size, int value);

int main()
{
	int n = 0;
	int m = 0;

	FILE *f = fopen("aib.in", "rt");
	FILE *g = fopen("aib.out", "wt");
	fscanf(f, "%i%i", &n, &m);
	int i;
	int *v = (int *)malloc(n * sizeof(int) + 1);
	int nr;
	for (i = 1; i <= n; i++)
	{
		fscanf(f, "%i", &nr);
		update(v, n, i, nr);
	}
	int op = 0, a = 0, b = 0, result = -1;
	for (; m; --m)
	{
		fscanf(f, "%i", &op);
		if (!op)
		{
			fscanf(f, "%i%i", &a, &b);
			update(v, n, a, b);
		}
		else
		{
			if (1 == op)
			{	
				fscanf(f, "%i%i", &a, &b);
				result = query(v, n, b) - query(v, n, a - 1);
				fprintf(g, "%i\n", result);
			}
			else
			{
				fscanf(f, "%i", &a);
				result = find(v, n, a);
				fprintf(g, "%i\n", result);
			}		
		}
	}
	fclose(f);
	fclose(g);

	return 0;
}

void update(int *v, int size, int index, int value)
{
	int zeros = 0;
	while (index <= size)
	{
		zeros = 0;
		v[index] += value;
		while (! (index & (1 << zeros)))
		{
			zeros++;
		}
	
		index += (1 << zeros);
	}

}

int query(int *v, int size, int index)
{
	int sum = 0;
	int zeros = 0;
	
	while (index > 0)
	{
		sum += v[index];
		zeros = 0;
		while (! (index & (1 << zeros)))
		{
			zeros++;
		}
		index -= (1 << zeros);

	}

	return sum;
	
}

int find(int *v, int size, int value)
{

	int pow = 1;
	for (; pow <= size; pow <<= 1);
	pow >>= 1;
	int index = 0;
	while (pow)
	{
		if (index + pow <= size && value >= v[index + pow])
		{
			value -= v[index + pow];
			if (!value)
			{
				return index + pow;
			}

			index += pow;
		}
		pow >>= 1;
	}
	return -1;
}