#include <iostream>
#include <fstream>

using namespace std;

int n, m, a[100010];

inline int Suma(int x)
{
    int s = 0;
    while(x)
    {
        s+=a[x];
        x-=(x&-x);
    }
    return s;
}

inline void Update(int x, int y)
{
    while(x<=n)
    {
        a[x]+=y;
        x+=(x&-x);
    }
}

inline int CautareBinara(int x)
{
    int mij, st, dr, s, sol, gasit = -1;
    st = 1;
    dr = n;
    while (st<=dr)
    {
        mij = (st + dr)/2;
        s = Suma(mij);
        if (s == x)
        {
            gasit = mij;
            dr = mij - 1;
        }
        else
            if (s > x)
                dr = mij - 1;
            else
                st = mij + 1;
    }
    if (gasit != -1)
        return gasit;
    return -1;
}

inline void Solve()
{
    ifstream f("aib.in");
    ofstream g("aib.out");
    f>>n>>m;
    int i, x, y, cod;
    for(i=1; i<=n; i++)
    {
        f>>x;
        Update(i, x);
    }
    int val1, val2;
    while(m)
    {
        m--;
        f>>cod>>x;
        if (cod!=2)
            f>>y;
        if (cod == 0)
            Update(x, y);
        else
            if (cod == 1)
            {
                val1 = Suma(y);
                val2 = Suma(x-1);
                g<<(val1-val2)<<"\n";
            }
            else
            {
                val1 = CautareBinara(x);
                g<<val1<<"\n";
            }
    }
    g.close();
}

int main()
{
    Solve();
    return 0;
}