#include <stdio.h>
#include <stdlib.h>
#define MAX 100001
#define in "aib.in"
#define out "aib.out"

unsigned int tree[MAX + 1], n ;

void insert(unsigned int index, unsigned int value)
{
	while (index <= n)
	{
		tree[index] += value;
		index += (index & -index);
	}
}


unsigned int sum(unsigned int index)
{
	unsigned int sum = 0;
	while (index > 0)
	{
		sum += tree[index];
		index -= (index & -index);
	}
	return sum;
}


unsigned int binary_search(unsigned int k, unsigned int total)
{
	unsigned int l = 1, r = k, m, s;
	while (l <= r) 
	{
		m = (l + r) / 2;	
		s = sum(m);
		if (total == s)
		{
			return m;
		}
		else if (total < s)
		{
			r = m - 1;
		}
		else 
		{
			l = m + 1;
		}
	}
	return 0;
}

unsigned int find_sum(unsigned int total)
{
	unsigned int l = binary_search(n, total);
	unsigned int k = 0;
	
	while (l != 0)
	{
		k = l;
		l = binary_search(l - 1, total);
	}	
	return k;
}

int main()
{
	unsigned int a[MAX], i, z, m, x, y;
	FILE *fin, *fout;
	
	if ((fin = fopen(in, "r")) == NULL)
	{
		printf("Eroare \n");
		exit(-1);
	}
	//read dimension of vectors
	fscanf(fin, "%d%d", &n, &m);

	//read the vectors
	for (i = 1; i<=n ; i++)
	{
		fscanf(fin, "%d", &a[i]);
		insert(i, a[i]);
	}
	fout = fopen(out, "w");
/*	for (i = 0; i <= n; i++)
		printf("%d ", tree[i]);		
	printf("\n");*/
	for (i = 0; i < m; i++)
	{
		fscanf(fin, "%d%d", &x, &y);
		if (x == 0)
		{
			fscanf(fin, "%d", &z);
			insert(y, z);
			//printf("Interval [%d %d] are maximul %d\n", y, z, j);
		}
		else if (x == 1)
		{
			fscanf(fin, "%d", &z);
			z = sum(z) - sum(y - 1);
			fprintf(fout, "%d\n", z);
			/*for (j = 0; j <= 2 * n + 1; j++) find(unsigned int node, unsigned int left, unsigned int right, unsigned int a, unsigned int b)
				printf("%d ", tree[j]);
			printf("\n");*/
		} else if (x == 2)
		{
			//printf("\n");
			z = find_sum(y);
			fprintf(fout, "%d\n", z == 0 ? -1 : z);
		}
	}
	fclose(fin);
	fclose(fout);
	return 0;
}