#include <stdio.h>

using namespace std;

int v[100005],n,m;

int least_sgn(int n)
{
    return ((n&(n-1))^n);
}

void add(int x, int y)
{
    while(x<=n)
    {
        v[x]+=y;
        x+=least_sgn(x);
    }
}

int sum(int x)
{
    int s=0,aux;
    while(x)
    {
        s+=v[x];
        x=x-least_sgn(x);
    }
    return s;
}

void cb(int st, int dr, int x, int& rez)
{
    if(st==dr) if(v[st]==x) {rez=st;return;}
               else return;
    int m=(st+dr)>>1;
    if(v[m]==x) {rez=m;return;}
    else if(x<v[m]) cb(st,m-1,x,rez);
    else cb(m+1,dr,x,rez);
}

int main()
{
    freopen("aib.in","r",stdin);
    freopen("aib.out","w",stdout);
    int i,t,a,b;
    scanf("%d%d",&n,&m);
    for(i=1;i<=n;i++)
    {
        scanf("%d",&a);
        add(i,a);
    }
    for(i=0;i<m;i++)
    {
        scanf("%d",&t);
        if(t==0)
        {
            scanf("%d%d",&a,&b);
            add(a,b);
        }
        else if(t==1)
        {
            scanf("%d%d",&a,&b);
            printf("%d\n",sum(b)-sum(a-1));
        }
        else
        {
            scanf("%d",&a);
            b=-1;
            cb(1,n,a,b);
            printf("%d\n",b);
        }
    }
    return 0;
}