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

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

int tree[100005], v[100005];
int n,m;

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

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

    dif = val - v[i];
    v[i] = val;

    while(i <= n)
    {
        tree[i] += dif;
        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 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]<<" ";

    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) modifica(a, v[a]+b);
        else if(opt==1) out<<(interog(b) - interog(a-1))<<"\n";
        else
        {
            for(j=1; j<=n; ++j)
                if(interog(j) == a)
                {
                    break;
                }
            if(j <= n) out<<j<<"\n";
            else out<<"-1\n";
        }
    }

    return 0;
}