#include<cstdio>
using namespace std;
int n,m,x,c,a,b,m1;
unsigned int AIB[100005];
void adauga(int x,int i)
{
    int ind=i;
    int poz=0;
    int p=1;
    while (ind<=n)
    {
        AIB[ind]+=x;
        while (!(p & ind))
        {
            poz++;
            p=(p<<1);
        }
        ind+=p;
        p=(p<<1);
        poz++;
    }
}
unsigned int suma(int x)
{
    int ind=x;
    int p=1;
    int poz=0;
   unsigned int sum=0;
    while (ind>0)
    {
        sum+=AIB[ind];
        while (!(ind & p))
        {
            p=(p<<1);
            poz++;
        }
        ind-=p;
        p=(p<<1);
        poz++;
    }
    return sum;
}
int main()
{
    freopen("aib.in","r",stdin);
    freopen("aib.out","w",stdout);
    scanf("%d%d",&n,&m1);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&x);
        adauga(x,i);
    }
    for(int i=1;i<=m1;i++)
    {
        scanf("%d",&c);
        if (!c)
        {
            scanf("%d%d",&a,&b);
            adauga(b,a);
        }
            else
        if (c==1)
        {
            scanf("%d%d",&a,&b);
            printf("%u\n",suma(b)-suma(a-1));
        }
            else
        {
            scanf("%d",&a);
            int ls=1;
            int ld=n;
            int k=-1;
            while(ls<=ld)
            {
                m=(ls+ld)/2;
                if (suma(m)==a)
                {
                    k=m;
                    break;
                }
                else
                if (suma(m)<a)
                {
                    ls=m+1;
                }
                else
                if (suma(m)>a)
                {
                    ld=m-1;
                }
            }
            printf("%d\n",k);
        }
    }
    return 0;
}