#include <iostream>
#include <fstream>

using namespace std;

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

const int NMAX = 1e5;

int n, q;
int x, y, tip;
int aib[NMAX+1];

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

int calc(int pos)
{
    int sum = 0;
    for(pos; pos>0; pos-=(pos&-pos))
        sum+=aib[pos];
    return sum;
}

int main()
{
    fin >> n >> q;
    for(int i=1; i<=n; i++)
    {
        fin >> x;
        update(i, x);
    }
    while(q--)
    {
        fin >> tip;
        if(tip == 0)
        {
            fin >> x >> y;
            update(x, y);
        }
        else if(tip == 1)
        {
            fin >> x >> y;
            fout << calc(y)-calc(x-1) << '\n';
        }
        else
        {
            fin >> x;
            int st = 1, dr = n;
            int ans = -1;
            while(st <= dr)
            {
                int mij = 1ll*(st+dr)/2;
                int sum = calc(mij);
                if(sum == x)
                    ans = mij;
                if(sum < x)
                    st = mij+1;
                else
                    dr = mij-1;
            }
            fout << ans << '\n';
        }
    }
    return 0;
}