#include <cstdio>

using namespace std;

int aib[100005], n;

inline int lsb(int x)
{
	return x & -x;
}

void update(int poz, int val)
{
	int i;
	for(;poz <= n; poz += lsb(poz))
		aib[poz] += val;
}
int query(int b)
{
	int s= 0;
	for(;b; b-=b & (-b))
		s += aib[b];
	return s;
}

int main()
{
    FILE *in, *out;
    in = fopen("aib.in", "r");
    out = fopen("aib.out", "w");
    int m, x, i, op, a, b, inc, sf, last, mij, aux;
    fscanf(in, "%d%d", &n, &m);
    for(i = 1; i <= n; i++)
    {
    	fscanf(in, "%d", &x);
    	update(i,x);
    }
	for(i = 1; i <= m; i++)
	{
		fscanf(in, "%d", &op);
		if(op == 0)
		{
			fscanf(in, "%d%d", &a, &b);
			update(a, b);
		}
		if(op == 1)
		{
			fscanf(in, "%d%d", &a, &b);
			fprintf(out, "%d\n", query(b) - query(a-1));
		}
		if(op == 2)
		{
			fscanf(in, "%d", &a);
			inc = 1;
			sf = n;
			last = -1;
			while(inc <= sf)
			{
				mij = (inc + sf) >> 1;
				aux = query(mij);
				if(aux >= a)
				{
					last = mij;
					sf = mij - 1;
				}
				else
					inc = mij + 1;
			}
			fprintf(out, "%d\n", last);
		}


	}
    return 0;
}