#include <cstdio>
#define bit(i) ((i)& (~i))
#define maxn 100001

int aib[maxn];

int n;

inline void update(int x, int v)
{
    for(;x<=n;x+=bit(x)) aib[x]+=v;
}

inline int query(int x)
{
    int s=0;
    for(;x;x-=bit(x)) s+=aib[x];
    return s;
}

inline int find(int v)
{
    int i, cnt;
    for(i=0, cnt=(1<<18); cnt ; cnt>>=1)
	if(i+cnt<=n)
	    if(v>=aib[i+cnt])
		i+=cnt, v-=aib[i];
    if(!v) return i;
    return -1;
}

int main()
{
    freopen("aib.in","r",stdin);
    freopen("aib.out","w",stdout);
    int m,i,v, type, p, q;
    scanf("%d %d\n",&n, &m);
    for(i=1;i<=n;++i)
    {
	scanf("%d ", &v);
	update(i, v);
    }

    while(m--)
    {
	scanf("%d ", &type);
	if(type==0)
	{
	    scanf("%d %d\n", &p, &q);
	    update(p, q);
	}
	if(type==1)
	{
	    scanf("%d %d\n", &p, &q);
	    printf("%d\n", query(q)-query(p-1));
	}
	if(type==2)
	{
	    scanf("%d\n", &p);
	    if(p==0) printf("-1\n");
	    else 
	    printf("%d\n",find(p)); 
	}


    }

    return 0;
}