#include <iostream>
#include <fstream>

using namespace std;
typedef long long ll;

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

const int nMax = 1e5 + 5e5 + 5;

int n, q;
ll a[nMax], aib[nMax];

void update(int x,ll val)
{
    for (int i = x;i <= n;i+=i&-i)aib[i] += val;
}

ll sum(int x)
{
    ll rez = 0;
    for (int i = x;i > 0;i-=i&-i)rez += aib[i];
    return rez;
}

int main()
{
    f >> n >> q;
    for (int i = 1;i <= n;i++){
        f >> a[i];
        update(i,a[i]);
    }

    for (int i = 1;i <= q;i++){
        int tip, x, y;
        f >> tip >> x;
        if (tip == 0){
            f >> y;
            update(x,y);
        }
        else if (tip == 1){
            f >> y;
            g << sum(y) - sum(x-1) << '\n';
        }
        else{
            int st = 1,dr = n;
            int mij;
            int rez = n + 1;
            while(st <= dr){
                mij = (st + dr) / 2;
                if (sum(mij) > x)dr = mij - 1;
                else if (sum(mij) < x)st = mij + 1;
                else{
                    rez = min(rez,mij);
                    dr = mij - 1;
                }
            }
            g << rez << '\n';
        }
    }
}