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

#define zero(x) ((x-1)^x)&x
int aib[100002],i,j,n,m,aux,a,b;
FILE *fin=fopen("aib.in","r"), *fout=fopen("aib.out","w");

void add(int val, int poz) {
	for(int i=poz;i>0;i-=zero(i)) {
		aib[i]+=val;
	}
}

int s(int poz) {
	int rez=0;
	for(int i=1;i<=poz;i+=zero(i)) {
		rez+=aib[i];
	}
	return rez;
}

int sum(int a, int b) {
	return s(b)-s(a);
}

int cota(int sum) {
	int lo,hi,mi;
	lo=1; hi=n;
	for(lo=1;lo<hi+1;) {
		mi=(lo+hi)>>1;
		if (aib[mi]>=sum) hi=mi;
		else if (sum>aib[mi]) lo=mi;
	}
	if (aib[lo]==sum) return lo;
	else if (aib[lo+1]==sum) return lo+1;	
	else return lo+2;
}

int main()
{
	fscanf(fin,"%i %i",&n,&m);
	for(i=1;i<=n;i++) {
		fscanf(fin,"%i",&aux);
		add(aux,i);
	}
	for(i=1;i<=m;i++) {
		fscanf(fin,"%i",&aux);
		if (aux==1) {
			fscanf(fin,"%i %i",&a,&b);
			fprintf(fout,"%i\n",sum(a,b));
		}
		else if (aux==0) {
			fscanf(fin,"%i %i",&a,&b);
			add(b,a);
		}
		else if (aux==2) {
			fscanf(fin,"%i",&a);
			fprintf(fout,"%i\n",cota(a));
		}
	}
	fclose(fout);	
	return 0;
}