#include <iostream>
#include <fstream>

using namespace std;

#define MAXN 100001

int N, M;
int tree[4 * MAXN + 100];

int updateValue;
int updatePlace;

void build(int, int, int);
void update(int, int, int);

int sumStart, sumEnd;
int sum;

void sumCalc(int, int, int);

int sumToFind, rollingSum;
int k, rollingK;

void sumFind(int, int, int);

int main()
{
	ifstream f("aib.in");
	ofstream g("aib.out");
	// Program
	f >> N >> M;
	for (int i = 1; i <= N; i++)
	{
		f >> updateValue;
		updatePlace = i;
		build(1, 1, N);
	}
	for (int i = 0; i < M; i++)
	{
		int c, a, b;
		f >> c;
		if (c == 0)
		{
			f >> a >> b;
			updatePlace = a;
			updateValue = b;
			update(1, 1, N);
		}
		else if (c == 1)
		{
			f >> a >> b;
			sumStart = a;
			sumEnd = b;
			sum = 0;
			sumCalc(1, 1, N);
			g << sum << '\n';
		}
		else
		{
			f >> a;

			sumToFind = a;
			rollingSum = 0;
			k = N;
			rollingK = 0;

			sumFind(1, 1, N);

			g << rollingK + k <<'\n';
		}
	}


	// Exit
	f.close();
	g.close();
	return 0;
}
void build(int treePlace, int treeStart, int treeEnd)
{
	if (treeStart == treeEnd)
	{
		tree[treePlace] = updateValue;
		return;
	}

	int mij = (treeStart + treeEnd) / 2;
	if (updatePlace <= mij) build(2 * treePlace, treeStart, mij);
	else build(2 * treePlace + 1, mij + 1, treeEnd);

	tree[treePlace] = tree[2 * treePlace] + tree[2 * treePlace + 1];
}
void update(int treePlace, int treeStart, int treeEnd)
{
	if (treeStart == treeEnd)
	{
		tree[treePlace] += updateValue;
		return;
	}

	int mij = (treeStart + treeEnd) / 2;
	if (updatePlace <= mij) update(2 * treePlace, treeStart, mij);
	else update(2 * treePlace + 1, mij + 1, treeEnd);

	tree[treePlace] = tree[2 * treePlace] + tree[2 * treePlace + 1];
}

void sumCalc(int treePlace, int treeStart, int treeEnd)
{
	if (sumStart <= treeStart && treeEnd <= sumEnd)
	{
		sum += tree[treePlace];
		return;
	}
	
	int mij = (treeStart + treeEnd) / 2;
	if (sumStart <= mij) sumCalc(2 * treePlace, treeStart, mij);
	if (mij + 1 <= sumEnd) sumCalc(2 * treePlace + 1, mij + 1, treeEnd);
}
void sumFind(int treePlace, int treeStart, int treeEnd)
{
	if (rollingSum + tree[treePlace] == sumToFind)
	{
		return;
	}

	//int mij = (treeStart + treeEnd) / 2;
	if (tree[treePlace] > (sumToFind-rollingSum))
	{
		k /= 2;
		if (k == 0)
		{
			k = -1;
			rollingK = 0;
			return;
		}
		sumFind(2 * treePlace, treeStart, treeEnd);
	}
	else //if (tree[treePlace] < sumToFind)
	{
		//     *
		//   /  \
		//  h    e
		if (k == N)
		{
			k = -1;
			rollingK = 0;
			return; // we have the highset sum, nothing to do
		}
		if (k == 1 && treePlace % 2 == 1)
		{
			k = -1;
			rollingK = 0;
			return; // we are a leaf and on the right and we want to go right... no can do
		}
		rollingK += k;
		rollingSum += tree[treePlace];
		//sumToFind -= tree[treePlace];

		sumFind(treePlace + 1, treeStart, treeEnd);

	}
}