#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <cstdlib>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
using namespace std;

int n, m, elem, query, a, b;
int aib[100001];

void update(int pos, int value){
	while(pos <= n){
		aib[pos] += value;
		pos += (pos & (-pos));
	}
}

int get(int pos){
	int sum = 0;
	while(pos > 0){
		sum += aib[pos];
		pos -= (pos & (-pos));
	}
	return sum;
}

int get_sum(int a, int b){
	return get(b) - get(a-1);
}

int search(int left, int right){
	int mid;
	if(left > right) 
		return -1;
	mid = left + (right - left) / 2;
	int g = get(mid);
	if(g == a){
		return mid;
	}
	if(g < a){
		return search(mid+1, right);
	}else{
		return search(left, mid-1);
	}
}


int main() 
{
	cin >> n >> m;
	for(int i = 0; i < n; i++){
		cin >> elem;
		update(i+1, elem);
	}
	for(int i = 0; i < m; i++){
		cin >> query;
		switch(query){
		case 0:
			cin >> a >> b;
			update(a, b);
			break;
		case 1:
			cin >> a >> b;
			cout << get_sum(a, b) <<"\n";
			break;
		case 2: 
			cin >> a;
			cout << search(1, n) << "\n";
		}
	}
	return 0;
}