#include <fstream>

using namespace std;

ifstream fin("aib.in");

ofstream fout("aib.out");

int aib[100005],N,M,a,x,y,p,b,st,dr,c,pos;

void update(int x,int pos)

{

    for(int i=pos;i<=N;i+=(i&(-i)))

        aib[i]+=x;

}

int suma(int pos)

{

    int s=0;

    for(int i=pos;i>0;i-=i&(-i))

        s+=aib[i];

    return s;

}

int verificare(int a)

{

    int st=1,dr=N;

    while(st<=dr)

    {

        int mijl=(st+dr)/2;

        if(suma(mijl)==a) return mijl;

        if(suma(mijl)<a) st=mijl+1;

        if(suma(mijl)>a) dr=mijl-1;

    }

    return -1;

}

int main()

{

    fin>>N>>M;

    for(int i=1;i<=N;i++)

    {

        fin>>p;

        update(p,i);

    }

    for(int i=1;i<=M;i++)

    {

        fin>>c;

        if(c==0)

        {

            fin>>a>>b;

            update(b,a);

        }

        else if (c==1)

        {

            fin>>a>>b;

            fout<<suma(b)-suma(a-1)<<"\n";

        }

        else if(c==2)

        {

            fin>>a;

            fout<<verificare(a)<<"\n";

        }

    }



    return 0;

}