#include <fstream>
using namespace std;

int n, m, v[100100], cit, op;

inline int fct(int a)
{
	return a & (-a);
}
void PUSH(int poz, int val)
{
	for (; poz <= n; poz += fct(poz))
		v[poz] += val;
}
inline int SUM(int poz)
{
	int ret = 0;
	for (; poz >= 1; poz -= fct(poz))
		ret += v[poz];
	return ret;
}

int main()
{
	ifstream f("aib.in");
	ofstream g("aib.out");
	
	f >> n >> m;
	for (int i = 1; i <= n; ++i)
	{
		f >> cit;
		PUSH(i, cit);
	}
	
	for (int i = 1; i <= m; ++i)
	{
		int a, b;
		f >> op;
		if (op == 0)
		{
			f >> a >> b;
			PUSH(a, b);
		}
		else
		if (op == 1)
		{
			f >> a >> b;
			g << SUM(b) - SUM(a - 1) << '\n';
		}
		else
		{
			f >> a;
			int j, cnt;
			for (j = 1, cnt = 1 << 20; cnt > 0; cnt >>= 1)
				if (j + cnt <= n)
					if (SUM(j + cnt) <= a) j += cnt;
			g << j << '\n';
		}
	}
}