#include <cstdio>

using namespace std;

#define NMAX 100005
#define zeros(i) (i&(-i))

int N,M;

int AIB[NMAX];

void Update(int val, int pos)
{
    for(int i=pos; i<=N; i+=zeros(i))
        AIB[i] += val;
}

int Query(int pos)
{
    int S = 0;

    for(int i=pos; i > 0; i-=zeros(i))
        S += AIB[i];

    return S;
}

int Search(int Sum)
{
    int left = 1;
    int right = N;
    int mid;
    int S = -1;

    while(left <= right)
    {

        mid = (left + right) >> 1;
        S = Query(mid);

        if(S == Sum)
            return mid;
        else
            if(S < Sum)
            {
                left = mid + 1;
            }
            else
            {
                right = mid - 1;
            }
    }

    return -1;
}

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

    scanf("%d%d",&N,&M);

    for(int i=1,x;i<=N;i++)
    {
        scanf("%d",&x);
        Update(x,i);
    }

    while(M--)
    {
        int op,a,b;

        scanf("%d%d",&op,&a);

        switch(op)
        {
            case 0:
                {
                    scanf("%d",&b);
                    Update(b,a);
                    break;
                }
            case 1:
                {
                    scanf("%d",&b);
                    printf("%d\n",Query(b)-Query(a-1));
                    break;
                }
            case 2:
                {
                    printf("%d\n",Search(a));
                    break;
                }
        }
    }
    return 0;
}