#include <cstdio>
#define p2(a) (((a^(a-1))+1)>>1)
#define dmax 100003
using namespace std;

int aib[dmax], n, m, k;

void update(int, int);
int sum(int, int);
void read();

void read()
{

    freopen("aib.in", "r", stdin);
    freopen("aib.out", "w", stdout);

    scanf("%i %i", &n, &m);
    for(int i=1; i<=n; i++)
        scanf("%i", &k), update(i, k);
}

void update(int a, int b)
{

    while(a<=n)
    {
        aib[a]+=b;
        a=a+p2(a);
    }
}

int sum(int a)
{
    int sum=0;
    for(; a>0; a-=p2(a))
        sum+=aib[a];
    return sum;
}

int sumk(int a, int st, int dr)
{

if(st==dr)
{
    if(sum(aib[st])==a)
        return st;
    else return -1;
}
else
{
    int mid=(st+dr+1)/2;
    if(sum(mid)==a) return mid;
    else if(sum(mid)>a) return sumk(a, mid, dr);
    else if(sum(mid)<a) return sumk(a, st, mid-1);
}

}

void solve()
{
    int a, b;
    for(int i=1; i<=m; ++i)
    {
        scanf("%i", &a);
        if(a==0)
        {
            scanf("%i%i", &a, &b);
            update(a, b);
        }
        else if(a==1)
        {
            scanf("%i%i", &a, &b);
            printf("%i\n", sum(b)-sum(a-1));
        }
        else if(a==2)
        {
            scanf("%i", &b);
            printf("%i\n", sumk(b, 1, n));
        }
    }

}
int main()
{
    read();
    solve();
    return 0;
}