#include <fstream>
#define nmax 100001

using namespace std;

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

int n, m;
int v[nmax];
int aib[nmax];

void adauga(int pozitie,int valoare)
{
    while (pozitie <= n)
    {
        aib[pozitie] += valoare;

        pozitie = pozitie +  (pozitie & -pozitie);
    }
}

int suma(int x)
{
    int sum = 0;
    while (x > 0)
    {
        sum += aib[x];
        x = x - (x&-x);
    }
    return sum;
}

int pozminim(int x)
{
    int p = 1;
    int q = n;
    while (p <= q)
    {
        int mij = (p + q)/2;
        if (suma(mij) == x)
            return mij;
        if (suma(mij) < x)
            p = mij + 1;
        else q = mij - 1;
    }
    return -1;
}

int main()
{
    fin >> n >> m;
    for (int i = 1; i <= n ; i++)
    {
        fin >> v[i];
        adauga(i,v[i]);
    }
    for (int i = 1; i <= m; i++)
    {
        int c;
        fin >> c;
        if (c == 0)
        {
            int a, b;
            fin >> a >> b;
            adauga(a,b);
        }
        else if (c == 1)
        {
            int a, b;
            fin >>a >> b;
            fout << suma(b) - suma(a-1) << "\n";
        }
        else
        {
            int x;
            fin >> x;
            fout << pozminim(x) << "\n";
        }
    }
}

//1 4 16 216 8