#include <iostream>
#include <fstream>

std::ifstream in("aib.in");
std::ofstream out("aib.out");

const int N=100000;

int v[N+1];
int AIB[N+2];

int parent(int i)
{
    return i-(i&(-i));
}

int frate_vecin(int i)
{
    return i+(i&(-i));
}

void update(int poz, int dif, int n)
{
    v[poz]+=dif;

    int casuta=poz+1;
    while(casuta<=n+1)
    {
        AIB[casuta]+=dif;
        casuta=frate_vecin(casuta);
    }
}

int sum(int poz)
{
    int s=0;

    int casuta=poz+1;
    while(casuta!=0)
    {
        s+=AIB[casuta];
        casuta=parent(casuta);
    }

    return s;
}

int interogare(int suma, int n)
{
    int st=1, dr=n+1, mij;

    while(st+1!=dr)
    {
        mij=(st+dr)/2;

        if(sum(mij)==suma)
            return mij;
        else if(sum(mij)<suma)
        {
            st=mij+1;
        }
        else
        {
            dr=mij;
        }
    }

    if(sum(st)!=suma) return -1;

    return st;
}

int main()
{
    int n, m, x, l, r;

    in>>n>>m;
    for(int i=1; i<=n; i++)
    {
        in>>x;
        update(i, x, n);
    }

    std::cout<<sum(2);

    for(int i=1; i<=m; i++)
    {
        in>>x;

        switch(x)
        {
        case 0:

            in>>l>>r;
            update(l, r, n);
            break;

        case 1:
            in>>l>>r;
            out<<sum(r)-sum(l-1)<<"\n";
            break;

        case 2:
            in>>x;
            out<<interogare(x, n)<<"\n";
            break;
        }
    }
}