#include <cstdio>

using namespace std;

int aib[100005];
int n;

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

int query(int p)
{
    int S = 0;

    for( ; p ; p -= p&(p-1)^p)
        S += aib[p];

    return S;
}

int bs(int st,int dr,int v)
{
    if(st > dr)
        return -1;

    int m = (st+dr)/2;
    int q = query(m);

    if(q == v)
        return m;

    if(v < q)
        return bs(st,m-1,v);

    if(v > q)
        return bs(m+1,dr,v);
}

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

    int m;
    scanf("%d%d",&n,&m);

    int i;
    int tmp;
    for(i = 1 ; i <= n ; ++i)
    {
        scanf("%d",&tmp);
        update(i,tmp);
    }

    int op,a,b;
    for(i = 1 ; i <= m ; ++i)
    {
        scanf("%d",&op);

        switch(op)
        {
        case 0:
            {
                scanf("%d%d",&a,&b);
                update(a,b);
                break;
            }
        case  1:
            {
                scanf("%d%d",&a,&b);
                printf("%d\n",query(b) - query(a-1));
                break;
            }
        case 2:
            {
                scanf("%d%d",&a);
                printf("%d\n",bs(1,n,a));
            }
        }
    }

    return 0;
}