#include <iostream>
#include <fstream>

using namespace std;
const int N = 100005;

#define int long long

ifstream f("aib.in");
ofstream g("aib.out");

int zero(int x) { return (x ^ (x - 1)) & x; }
int n, v[N], aib[N], m;

void add(int a, int b) {
	for (int i = a; i <= n; i += zero(i))
		aib[i] += b;
}

int query(int a) {
	//suma elem pana la poz a
	int sum = 0;
	for (int i = a; i > 0; i -= zero(i))
		sum += aib[i];
	return sum;
}

signed main()
{ 
	f >> n>>m;
	for (int i = 1; i <= n; i++)
	{
		f >> v[i];
		add(i, v[i]);
	}
	while (m--) {
		int tip;
		f >> tip;
		if (tip == 0) {
			int a, b;
			f >> a >> b;
			add(a,b);
		}
		else if (tip == 1){
			int a, b;
			f >> a >> b;
			g << query(b) - query(a - 1) << "\n";
		}
		else {
			int a;
			f >> a;
			int st = 1; 
			int dr = n;
			int sol = -1;
			while (st < dr) {
				int mij = (st + dr) / 2;
				if (query(mij) == a)
				{
					sol = mij;
					dr = mij - 1;
				}
				else if (query(mij) > a)
					dr = mij -1;
				else
					st = mij+1;
			}
			if (sol != 0)
				g << sol << "\n";
			else
			{
				g << st << "\n";
			}

		}
	}


}