#include <iostream>
#include <cstdio>

using namespace std;

const int NMax = 100005;
int aib[NMax], x, y, N, M;

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 suma(int numar)
{
    int sum = 0;
    while(numar)
    {
        sum += aib[numar];
        numar=numar-zero(numar);
    }

    return sum;
}

void Binary()
{
    int st=1, dr=N;
    int mij;

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

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

        else
            if(sum < x)
                st = mij+1;

        else
            dr = mij-1;
    }

    printf("-1\n");
}

void Read()
{
    scanf("%d %d", &N, &M);

    for(int i=1; i<=N; ++i)
    {
        int k;
        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=suma(y);
            int s2=suma(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;
}