#include <fstream>

#define zero(x) ((x^(x-1))&x)
#define Nmax 1000000

using namespace std;
ifstream fin("aib.in");
ofstream fout("aib.out");


int x,n,i,m,t,a,b;

int aib[100010];

void Add(int a,int b)
{
    for(int i=a;i<=n;i+= zero(i))
    {
        aib[i]+=b;
    }
}

int Sum(int a)
{
    int summ=0;
    for(int i=a;i>0;i-=zero(i))
        summ+=aib[i];
    return summ;
}

int binarySearch(int target)
{
    int in=1,s=0;
    int sf=n;
    int mij=(in+sf)/2;

    while(in<=sf)
    {
        s=Sum(mij);
        if(s<target)
            in=mij+1;
        if(s>target)
            sf=mij-1;
        if(s==target)
            return mij;
        mij=(in+sf)/2;
    }
    return -1;
}

int main()
{

    fin>>n>>m;

    for(i=1;i<=n;i++)
    {
        fin>>t;
        Add(i,t);
    }


    for(i=1;i<=m;i++)
    {
        fin>>t>>a;
        if(t==0)
        {
            fin>>b;
            Add(a,b);
        }
        else
            if(t==1)
            {
                fin>>b;

                fout<<Sum(b)-Sum(a-1)<<'\n';

            }
            else
            {
                fout<<binarySearch(a)<<'\n';
            }
    }



    return 0;
}