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

clock_t start=clock();

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

int N, M;
int aib[100011];

void update(int idx, int val)
{   while(idx <= N)
    {   aib[idx] += val;
        idx += (idx & -idx);
    }
}

int query(int idx)
{   int ans = 0;
    while(idx > 0)
    {   ans += aib[idx];
        idx -= (idx & -idx);
    }
    return ans;
}

int bin_search(int sv)
{   int qv, pos = -1;
    int st, dr, mid;

    st = 1; dr = N;
    while(st <= dr)
    {   mid = (st + dr) / 2;
        qv = query(mid);

        if(qv == sv)
        {   pos = mid;
            dr = mid - 1;
        }
        else if(qv < sv)
            st = mid + 1;
        else dr = mid - 1;
    }

    return pos;
}


int main()
{   int i, a, b, op;

    f>>N>>M;
    for(i = 1; i <= N; i++)
    {   f>>a;
        update(i, a);
    }
    for(i = 1; i <= M; i++)
    {   f>>op;
        if(op == 0)
        {   f>>a>>b;
            update(a, b);
        }
        else if(op == 1)
        {   f>>a>>b;
            g<<query(b) - query(a - 1)<<'\n';
        }
        else
        {   f>>a;
            g<<bin_search(a)<<'\n';
        }
    }

    cout << 1.0*(clock()-start)/(1.0*CLOCKS_PER_SEC) << '\n';
    f.close();
    g.close();
    return 0;
}