#include <iostream>
#include <fstream>
#define zeros(x) ((x^(x-1))&x)

using namespace std;

const int NMAX = 100001;
int AIB[NMAX];
int SUM[NMAX];
int n,m;

void Add(int,int);
void citire()
{
   scanf("%d %d",&n,&m);
    int x;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&x);
        Add(i,x);
    }
}

void Add(int x,int val)
{
    for(int i=x;i<=n;i+=zeros(i))
        AIB[i]+=val;
}

int Sum(int x)
{
    int sum = 0;
    for(int i=x;i>0;i-=zeros(i))
        sum+=AIB[i];
    return sum;
}

void sum_partial()
{
    for(int i=1;i<=n;i++)
        SUM[i] = Sum(i);
}

int binar(int a)
{
    int x = 1,y=n;
    int m;
    while(x<=y)
    {
        m = (x+y)/2;
        if(SUM[m]==a && SUM[m-1] < a)
            return m;
        else
        {
            if(SUM[m] >= a)
                y = m-1;
            else
                x = m+1;
        }
    }
    return -1;
}

int main()
{
    freopen("aib.in","r",stdin);
    freopen("aib.out","w",stdout);
    citire();
    int q,a,b;
    for(int i=1;i<=m;i++)
    {
        scanf("%d",&q);
        if(q==0)
        {
            scanf("%d %d",&a,&b);
            Add(a,b);
            continue;
        }
        if(q==1)
        {
            scanf("%d %d",&a,&b);
            printf("%d\n",Sum(b)-Sum(a-1));
            continue;
        }
        if(q==2)
        {
            scanf("%d",&a);
            sum_partial();
            printf("%d\n",binar(a));
            continue;
        }
    }
   fclose(stdin);
   fclose(stdout);
    return 0;
}