#include <fstream>
#include <vector>

using namespace std;

class AIB
{
	vector<int> _container;
	int leftIndex(int i)
	{
		return (i ^ (i - 1)) & i;
	}
public:
	AIB(int size)
	{
		_container.resize(size + 1, 0);
	}
	void Add(int index, int value)
	{
		for (int i = index; i < _container.size(); i += leftIndex(i))
		{
			_container[i] += value;
		}
	}
	int Query(int index)
	{
		int sum = 0;
		for (int i = index; i > 0; i -= leftIndex(i))
		{
			sum += _container[i];
		}
		return sum;
	}
	int getMinIndex(int sum)
	{
		int idx = 1 << (int)floor(log2(_container.size() - 1));
		int s = Query(idx);
		while (s > sum)
		{
			idx >>= 1;
			s = Query(idx);
		}
		while (s < sum && ((idx & 1) == 0))
		{
			idx += leftIndex(idx) >> 1;
			s = Query(idx);
		}
		if (s != sum)
		{
			idx = idx ^ leftIndex(idx);
			for (int i = 0; (1 << i) < idx && s != sum; i++)
			{
				idx += 1 << i;
				s = Query(idx);
			}
		}
		/*while (s != sum && idx > 0)
		{
			if (s > sum)
			{
				idx >>= 1;
			}
			else
			{
				idx += (leftIndex(idx) >> 1);
			}
			s = Query(idx);
		}*/
		return idx;
	}
};

int main()
{
	int N, M, x, y, z;
	vector<int> v;
	
	ifstream f("aib.in");
	ofstream g("aib.out");
	f >> N >> M;
	AIB aib(N);

	for (int i = 1; i <= N; i++)
	{
		f >> x;
		aib.Add(i, x);
	}
	for (; M > 0; M--)
	{
		f >> x >> y;
		if (x < 2)
		{
			f >> z;
		}
		if (x == 0)
		{
			aib.Add(y, z);
		}
		if (x == 1)
		{
			g << aib.Query(z) - aib.Query(y - 1) << "\n";
		}
		if (x == 2)
		{
			g << aib.getMinIndex(y) << "\n";
		}
	}
	
}