#include <fstream>
#define lung(x) ( (x^(x- 1)) & x )
using namespace std; 

ifstream fin("aib.in");
ofstream fout("aib.out"); 

int N, M; 
int aib[100100]; 

void update(int val, int poz) {
	for (int i = poz; i <= N; i += lung(i))
		aib[i] += val; 
}

int query(int poz) {
	int s = 0; 
	for (int i = poz; i >= 1; i -= lung(i))
		s += aib[i]; 

	return s; 
}

int search(int a) {
	int mid, st = 1, dr = N, sol = -1; 
	while (st <= dr) {
		mid = (st + dr) / 2; 
		if (query(mid) == a) {
			sol = mid;
			dr = mid - 1; 
		}

		else if (query(mid) > a)
			dr = mid - 1;

		else
			st = mid + 1; 
	}
	return sol; 
}

int main()
{
	fin >> N >> M;
	for (int i = 1; i <= N; i++)
	{
		int x; 
		fin >> x; 
		update(x, i); 
	}

	int q, a, b; 
	for (int i = 1; i <= M; i++) {
		fin >> q; 
		if (q == 1) {
			fin >> a >> b; 
			update(b, a); 
		}

		if (q == 2) {
			fin >> a >> b; 
			fout << query(b) - query(a) - 1 << '\n';
		}

		if (q == 3) {
			fin >> a; 
			fout << search(a) << '\n';
		}
	}

	return 0; 
}