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


#define zeros(x) x&(-x)

int n, m,v[100001];
int aib[100001];


int sumAIB(int x)
{
	int s = 0;
	while (x)
	{
		s += aib[x];
		x &= (x - 1);
	}
	return s;
}
void createAIB()
{
	for (int i = 1; i <= n; i++)
	{
		aib[i] =v[i];
		if (!(i & 1))
		{
			int r =zeros(i);
			aib[i] += sumAIB(i - 1) - sumAIB(i - r );
		}
	}
}

void updateAIB(int deAdaugat,int pos)
{
	
	int i = pos;
	while (i <= n)
	{
		int pas = zeros(i);
		aib[i] += deAdaugat;
		i += pas;
	}
}
int binarySearchAIB(int elem,int l,int r)
{
	if (l > r)
		return -1;
	int m = (l + r) / 2;
	int suma = sumAIB(m);
	if (suma == elem)
		return m;
	if (suma > elem)
		return binarySearchAIB(elem, l, m);
	else
		return binarySearchAIB(elem, m + 1, r);
}

int main()
{
	freopen("aib.in", "r", stdin);
	freopen("aib.out", "w", stdout);



	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &v[i]);
	}
	int r = zeros(6);

	createAIB();

	int a, b, c;
	for (int k = 0; k < m; k++)
	{
		scanf("%d%d", &a, &b);
		if (a != 2)
		{
			scanf("%d", &c);
			if (a == 0)
			{
				updateAIB(c, b);
			}
			else
			{
				printf("%d\n", sumAIB(c) - sumAIB(b - 1));
			}
		}
		else
			printf("%d\n", binarySearchAIB(b, 1, n));
	}
}