#include<fstream>
#define NMax 100005
using namespace std;
ifstream fin("aib.in");
ofstream fout("aib.out");

int N,M;
int AIB[NMax];

int Query(int poz)
{
    int Sum = 0;

    for(int i = poz ; i ; i -= (i & (-i)) )
        Sum += AIB[i];

    return Sum;
}

void Update(int Val,int poz)
{
    for(int i = poz ; i <= N ; i += (i & (-i)) )
        AIB[i] += Val;
}

void Read()
{
    fin>>N>>M;

    for(int i = 1 ; i <= N ; ++i)
    {
        int x;  fin>>x;
        Update(x,i);
    }
}

void Solve()
{
    for(int i = 1 ; i <= M ; ++i)
    {
        int t,a,b; fin>>t;

        switch(t)
        {
            case 0 :
                fin>>a>>b;
                Update(b,a);
            break;

            case 1 :
                fin>>a>>b;
                fout<<( Query(b) - Query(a-1) )<<"\n";
            break;

            case 2 :
                fin>>a;

                int l = 0,r = N + 1,mid,sol = -1;

                while(l <= r)
                {
                    mid = (l+r) / 2;
                    int Sum = Query(mid);

                    if(Sum == a)
                    {
                        sol = mid;
                        r = mid - 1;
                    }
                    else
                        if(Sum < a) l = mid + 1;
                        else    r = mid - 1;
                }

                fout<<sol<<"\n";
            break;
        }
    }
}

int main()
{
    Read();
    Solve();

    fin.close();
    fout.close();
    return 0;
}