#include <cstdio>
#define LSB(x) ( x&(-x) )
using namespace std;
int i,j,m,n,AIB[100005],x,y,k,x1,x2,y1;
void update(int x, int i)
{
    int ii;
    for(ii=1; ii<=n; ii+=LSB(ii))
    AIB[ii]+=x;
}
int query(int p)
{
    int i,k=0;
    for(i=p; i>0; i-=LSB(i))
        k+=AIB[i];
    return k;
}
int bs(int x)
{

    int st,dr,m,sol;
    st=1; dr=n;
    while(st<=dr)
    {
        m=(st+dr)/2;
        sol=query(m);
        if(sol==x) return m;
        if(sol<x) st=m+1;
        else dr=m-1;
    }
    return -1;
}
int main()
{
    freopen("aib.in","r",stdin);
    freopen("aib.out","w",stdout);
    scanf("%d %d",&n,&m);
    for(i=1 ;i<=n; i++)
    {
        scanf("%d",&x);
        update(x,i);
    }

    for(i=1; i<=m; i++)
    {
        scanf("%d",&y);
        if(y==0)
        {
            scanf("%d %d",&x1,&y1);
            update(x1,y1);
        }
        if(y==1)
        {
            scanf("%d %d",&x1,&y1);
            printf("%d\n", query(y1)-query(x1-1));
        }
        if(y==2)
        {
            scanf("%d",&x1);
            bs(x1);
        }
    }
    return 0;
}