#include <fstream>

using namespace std;

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

int n, m, aib[100005];

int ub(int x){
    return (x&(-x));
}

void add(int poz, int val)
{
    for(int i = poz; i <= n; i += ub(i))
        aib[i] += val;
}

int sum(int poz)
{
    int ans = 0;
    for(int i = poz; i >= 1; i -= ub(i))
        ans += aib[i];

    return ans;
}

int main()
{
    f >> n >> m;
    for(int i = 1; i <= n; i ++)
    {
        int x; f >> x;
        add(i, x);
    }

    for(int i = 1; i <= m; i ++)
    {
        int x, y, tip; f >> tip;
        if(tip == 0){
            f >> x >> y;
            add(x, y);
        }

        else if(tip == 1){
            f >> x >> y;
            g << sum(y) - sum(x - 1) << '\n';
        }

        else
        {
            f >> x;

            int st = 1, dr = n, poz = -1;
            while(st <= dr && poz == -1)
            {
                int mij = (st + dr) / 2;

                if(sum(mij) < x)
                    st = mij + 1;

                else if(sum(mij) > x)
                    dr = mij - 1;

                else
                    poz = mij;
            }

            g << poz << '\n';
        }
    }
    return 0;
}