#include <iostream>

#define NMax 100000

using namespace std;

int N, ArbInt[4*NMax];

void Update (int K, int L, int R, int P, int V)
{
    int Mid=(L+R)/2;
    if (L==R)
    {
        ArbInt[K]+=V;
        return;
    }
    if (P<=Mid)
    {
        Update (2*K, L, Mid, P, V);
    }
    else
    {
        Update (2*K+1, Mid+1, R, P, V);
    }
    ArbInt[K]=ArbInt[2*K]+ArbInt[2*K+1];
}

int Query (int K, int L, int R, int QL, int QR)
{
    int Mid=(L+R)/2;
    if (L==QL and R==QR)
    {
        return ArbInt[K];
    }
    if (QR<=Mid)
    {
        return Query (2*K, L, Mid, QL, QR);
    }
    if (QL>Mid)
    {
        return Query (2*K+1, Mid+1, R, QL, QR);
    }
    return Query (2*K, L, Mid, QL, Mid)+Query (2*K+1, Mid+1, R, Mid+1, QR);
}

int QueryK (int K, int L, int R, int Q)
{
    int Mid=(L+R)/2;
    if (L==R)
    {
        if (Q!=ArbInt[K])
        {
            return -1;
        }
        return Mid;
    }
    if (Q<=ArbInt[2*K])
    {
        return QueryK (2*K, L, Mid, Q);
    }
    Q-=ArbInt[2*K];
    return QueryK (2*K+1, Mid+1, R, Q);
}

int main()
{
    freopen ("aib.in", "r", stdin);
    freopen ("aib.out", "w", stdout);
    int NQ;
    scanf ("%d %d", &N, &NQ);
    for (int i=1; i<=N; ++i)
    {
        int X;
        scanf ("%d", &X);
        Update (1, 1, N, i, X);
    }
    for (; NQ>0; --NQ)
    {
        int Type, Q1, Q2;
        scanf ("%d %d", &Type, &Q1);
        if (Type==0)
        {
            scanf ("%d", &Q2);
            Update (1, 1, N, Q1, Q2);
        }
        if (Type==1)
        {
            scanf ("%d", &Q2);
            printf ("%d\n", Query (1, 1, N, Q1, Q2));
        }
        if (Type==2)
        {
            printf ("%d\n", QueryK (1, 1, N, Q1));
        }
    }
    return 0;
}