#include <iostream>
#include <fstream>
#include <vector>
#include <functional>
#include <algorithm>
#define MAX_N 100001
#define pas(x) (x ^ (x-1) & x)
using namespace std;
ifstream f("aib.in");
ofstream g("aib.out");
int n, m,aib[MAX_N];
void update_aib(int cur, int value)
{
	for (int i=cur; i<=MAX_N; i+=pas(i))
	{
		aib[i] += value;
	}
}
int search_aib(int cur)
{
	int answer = 0;
	for (int i = cur; i >= 1; i-=pas(i))
	{
		answer += aib[i];
	}
	return answer;
}
int main()
{
	//cout << pas(8);
	f >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		int x;
		f >> x;
		update_aib(i, x);
	}
	//cout << "DA";
	for (int i = 1; i <= m; i++)
	{
		int type=0, a=0, b=0;
		//cout << i << '\n';
		f >> type;
		if (type == 0)
		{
			f >> a >> b;
			update_aib(a, b);
		}
		else if (type == 1)
		{
			f >> a >> b;
			g << search_aib(b) - search_aib(a - 1) << '\n';
		}
		else 
		{ 
			f >> a;
			int li=1, ls=n, lm=0,ok=0;
			while (li <= ls && !ok)
			{
				lm = (li + ls) / 2;
				if (search_aib(lm) > a)
				{
					ls = lm - 1;
				}
				else if (search_aib(lm) == a)
				{
					ok = 1;
				}
				else li = lm + 1;
			}
			g << lm << '\n';
		}
	}
	return 0;
}