#include <fstream>

using namespace std;

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

int n, m, x, aib[100005], a, b, cer;

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

void adaugare(int poz, int x)
{
    for(int i=poz; i<=n;)
    {
        aib[i]+=x;
        i=i+zero(i);
    }
}

int determinare(int poz)
{
    int sum=0;
    for(int i=poz; i>0;)
    {
        sum+=aib[i];
        i=i-zero(i);
    }
    return sum;
}

int cautBinar(int lg, int x)
{
    int i;
    for(i=n; lg > 0; lg>>=1)
        if(i-lg > 0 && determinare(i-lg) >= x)
            i-=lg;
    if(determinare(i) == x)
        return i;
    return -1;
}

int main()
{
    f>>n>>m;

    for(int i=1; i<=n; i++)
    {
        f>>x;
        adaugare(i, x);
    }
    int lg=0;
    for(lg=1; lg<=n; lg<<=1);

    for(int i=1; i<=m; i++)
    {
        f>>cer;
        if(cer == 0)
        {
            f>>a>>b;
            adaugare(a, b);
        }
        if(cer == 1)
        {
            f>>a>>b;
            g<<determinare(b)-determinare(a-1)<<'\n';
        }
        if(cer == 2)
        {
            f>>a;
            g<<cautBinar(lg, a)<<'\n';
        }
    }

    return 0;
}