#include <cstdio>
#include <cmath>
#include <climits>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <bitset>
#include <map>
#include <cstring>
#include <algorithm>

#define NMAX 100003

using namespace std;

FILE* fin, * fout;

int n, m;
long long int aib[NMAX];
void add(int x, int poz)
{
	for (int i = poz; i <= n; i += (i & (-i))) {
		aib[i] += x;
	}
}
long long getSumAtPoz(int poz)
{
	long long int s = 0;
	for (int i = poz; i >= 1; i -= (i & (-i))) {
		s += aib[i];
	}
	return s;
}

void cBin(int sum)
{
	int st = 1, dr = n, sol = -1;
	while (st <= dr)
	{
		int mij = (st + dr) / 2;
		int val = getSumAtPoz(mij);
		if (val == sum)
		{
			sol = mij;
			dr = mij - 1;
		}
		else if (val < sum)
		{
			st = mij + 1;
		}
		else {
			dr = mij - 1;
		}
	}
	if (sol != -1)
	{
		fprintf(fout, "%d\n", sol);
		return;
	}
	fprintf(fout, "-1\n");
}

int main()
{
	fin = fopen("aib.in", "r");
	fout = fopen("aib.out", "w");

	fscanf(fin, "%d %d", &n, &m);
	for (int i = 1; i <= n; i++)
	{
		int x;
		fscanf(fin, "%d", &x);
		add(x, i);
	}
	for (int i = 1; i <= m; i++)
	{
		int cerinta;
		fscanf(fin, "%d", &cerinta);
		if (cerinta == 0)
		{
			int x, poz;
			fscanf(fin, "%d %d", &poz,&x);
			add(x, poz);
		}
		else if (cerinta == 1)
		{
			int a, b;
			fscanf(fin, "%d %d", &a, &b);
			fprintf(fout, "%lld\n", getSumAtPoz(b) - getSumAtPoz(a - 1));
		}
		else {
			int x;
			fscanf(fin, "%d", &x);
			cBin(x);
		}
	}
	return 0;
}