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

int a,b,x,N,M,tree[100100];

int rightbit (int x)
{
    return ((x^(x-1))&x);
}

void add(int a, int b)
{
    int k = a;
    while(k<=N)
    {
        tree[k]+=b;
        k+=rightbit(k);
    }
}

int sum(int a)
{
    int ret = 0;
    int k = a;
    while(k)
    {
        ret+=tree[k];
        k-=rightbit(k);
    }
    return ret;
}

int caut(int a)
{
    int step=1;
    do
    {
        step*=2;
    }while(step<=N);

    for(int i=0;step>0;step/=2 )
         if(i+step<=N)
            if(a>=tree[i+step])
            {
                i+=step;
                a-=tree[i];

                if (a==0)
                    return i;
            }

    return -1;
}

int main()
{
    freopen("aib.in","r",stdin);
    freopen("aib.out","w",stdout);
    scanf("%d%d",&N,&M);
    for(int i=1;i<=N;++i)
    {
        scanf("%d",&x);
        add(i,x);
    }


    for(int i=1;i<=M;++i)
    {
        scanf("%d",&x);
        if(x==0)
        {
            scanf("%d%d",&a,&b);
            add(a,b);
        }
        if(x==1)
        {
            scanf("%d%d",&a,&b);
            printf("%d\n",sum(b)-sum(a-1));
        }
        if(x==2)
        {
            scanf("%d",&a);
            printf("%d\n",caut(a));
        }
    }

    return 0;
}