#include <string>
#include <stdio.h>
#include <iostream>
#include <fstream>
#include <ctime>
using namespace std;

int main() {
	int i, *AIB, min, m, n, op, num, sum, dif, cp, search, right = 1, max = 1, left, certain, step, j, val;
	ifstream f1;
	ofstream f2;
	f1.open("aib.in");
	f2.open("aib.out");
	f1 >> m >> n;
	int t1, t2;
	t1 = time(0);
	bool *v = new bool[m];
	for(cp = m; cp >>= 1; max <<= 1);
	max <<= 1;
	AIB = new int[max + 1];

	for(int iteratii = 0; iteratii < m; iteratii++) {
		f1 >> val;
		for (int i = iteratii + 1; i <= max; i += (i & (-i))) {
			        AIB[i] += val;
		}
	}
	

	for(int iteratii = 0; iteratii < n; iteratii++) {
		f1 >> op;
		switch(op) {
			case 0:
				f1 >> num >> val;
			    for (int i = num; i <= max; i += (i & (-i))) {
			        AIB[i] += val;
			    }
				break;

			case 1:
				f1 >> left >> right;
				// f2 << left << " " << right << endl;
				left--;
				right;
				sum = 0;
				while(left != right) {
					if(right > left) {
						sum += AIB[right];
						right -= (right & (-right));
					}
					else {
						sum -= AIB[left];
						left -= (left & (-left));
					}
				}
				f2 << sum << endl;
				break;
				

			case 2:
				f1 >> search;
				step = max >> 1, certain = 0;
				for(j = 0; step; step >>= 1) {
					if(AIB[j + step] <= search) {
						if(AIB[j + step] == search) {
							certain = j + step;
							continue;						
						}
						search -= AIB[j + step], j += step;
					}						
				}
				f2 << certain << endl;
				break;
		}
		
	}
	f1.close();
	f2.close();
	delete[] AIB;
	delete[] v;
	return 0;
}