#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

#define stinl static inline
#define MAX_N 100005

namespace Fenwick {
	int N, tree[MAX_N];

	stinl void add(int i, int val) {
		for (; i <= N; i += i & (-i))
			tree[i] += val;
	}

	stinl void init(int N, int* arr) {
		Fenwick::N = N;
		for (int i = 1; i <= N; i++)
			add(i, arr[i]);
	}

	stinl long long query(int i) {
		long long sum = 0;
		for (; i > 0; i -= i & (-i))
			sum += tree[i];
		return sum;
	}
}

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

int N, M, x[MAX_N], i;
int type, a, b;
int low, high, mid, sol;

int main() {
	fin >> N >> M;
	for (i = 1; i <= N; i++)
		fin >> x[i];

	Fenwick::init(N, x);

	for (i = 1; i <= M; i++) {
		fin >> type >> a;
		if (type < 2) fin >> b;

		if (type == 0) Fenwick::add(a, b);
		else if (type == 1)
			fout << Fenwick::query(b) - Fenwick::query(a - 1) << '\n';
		else {
			low = 1, high = N, sol = 0;
			while (low <= high) {
				mid = (low + high) / 2;
				if (Fenwick::query(mid) >= a) {
					sol = mid;
					high = mid - 1;
				}
				else low = mid + 1;
			}
			
			fout << sol << '\n';
		}
	}

	fin.close();
	fout.close();
	return 0;
}