#include <iostream>
#include <cstdio>

using namespace std;

const int Nmax = 100005;
const int Mmax = 150005;

int n,m,aib[Nmax],x,y,k;

int zero(int numar)
{
    return (((numar^(numar-1))&numar));
}

void Inserare(int numar, int ind)
{
    for(int i=numar; i<=n; i=i+(zero(i)))
        aib[i]+=ind;
}

int sum(int numar)
{
    //sum de la 1 la y - sum de la 1 la x

    int s1=0;

    while(numar)
    {
        s1+=aib[numar];
        numar=numar-zero(numar);
    }

    return s1;
}

void binary()
{
    int st=1;
    int dr=n;
    int mij;

    while(st<=dr)
    {
        mij=(st+dr)>>1;
        int suma=sum(mij);

        if(suma==x)
        {
            printf("%d\n",mij);
            return;
        }

        else
            if(suma>x)
                dr=mij;

        else
            st=mij+1;

    }

    printf("-1");
}

void Read()
{
    scanf("%d%d", &n, &m);

    for(int i=1; i<=n; ++i)
    {
        scanf("%d", &k);
        Inserare(i,k);
    }

    for(int i=1; i<=m; ++i)
    {
        int t;
        scanf("%d", &t);

        if(t==0)
        {
            scanf("%d%d", &x,&y);
            Inserare(x,y);
        }

        else if(t==1)
        {
            scanf("%d%d", &x,&y);

            int s1=sum(y);
            int s2=sum(x-1);

            printf("%d\n",s1-s2);
        }

        else
        {
            scanf("%d",&x);
            binary();
        }
    }
}

int main()
{
    freopen("aib.in", "r", stdin);
    freopen("aib.out", "w", stdout);

    Read();

    return 0;
}