#include<iostream>
#include<fstream>
using namespace std;

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

int tree[100005];
int n,m;

int calc_fii(int x)
{
    return ((x ^ (x - 1)) & x);
}

void modifica(int i, int val)
{
    int dif;

    while(i <= n)
    {
        tree[i] += val;
        i += calc_fii(i);
    }
}

int interog(int i)
{
    int r;

    r=0;
    while(i > 0)
    {
        r += tree[i];

       i -= calc_fii(i);
    }

    return r;
}

int caut(int val)
{
    int i,salt;

    salt=1;
    while(salt<=n) salt *= 2;
    salt /= 2;

    //for(int i=1; i<=n; ++i) cout<<tree[i]<<" "; cout<<"\n";
    //cout<<"val="<<val<<"    salt="<<salt<<"\n";

    i=0;
    while(salt>0)
    {
        //cout<<"tree["<<i<<"+"<<salt<<"] = "<<tree[i+salt]<<"    val="<<val<<"\n";

        if(val >= tree[i+salt] && i+salt <= n) /// Daca am gasit o suma mai mica ce apartine vectorului
        {
            val -= tree[i+salt]; /// Scad suma cautata
            i += salt; /// Ma repozitionez

            //cout<<"Am scazut val = "<<val<<"\n";

            if(val == 0) return i; /// Am gasit suma, dupa ce am compus-o sumele partiale scazute anterior
        }
        salt /= 2;
    }

    return -1; /// N-am gasit suma
}

int main()
{
    int i,opt,a,b,x,j;

    in>>n>>m;
    for(i=1; i<=n; ++i) /// Citesc n elemente
    {
        in>>x;
        modifica(i, x);
    }

    //for(i=1; i<=n; ++i) cout<<tree[i]<<" ";

    int cnt=0;
    for(i=1; i<=m; ++i) /// Efectuez m interogari/modificari
    {
        in>>opt; /// opt = 0 --> calculez suma [a, b]
                 /// opt = 1 --> elementul v[a] devine b (arborele se modifica)
        in>>a;
        if(opt < 2) in>>b;

        //if(opt>0) ++cnt; if(cnt == 498) cout<<opt<<" "<<a<<" "<<b<<"\n";

        if(opt==0) modifica(a, b);
        else if(opt==1) out<<(interog(b) - interog(a-1))<<"\n";
        else
        {
            out<<caut(a)<<"\n";

            /*for(j=1; j<=n; ++j)
                if(interog(j) == a)
                {
                    break;
                }
            if(j <= n) out<<j<<"\n";
            else out<<"-1\n";*/
        }
    }

    return 0;
}