#include <cstdio>

using namespace std;
int aib[100010],n;
inline void upgrade(int poz,int val)
{
    for(; poz<=n; poz+=poz&-poz)
        aib[poz]+=val;
}
inline int query(int poz)
{
    int s=0;
    for(; poz>=1; poz-=poz&-poz)
        s+=aib[poz];
    return s;
}
inline int caut(int x)
{
    int st=1,dr=n,med,val;
    while(st<=dr)
    {
        med=(st+dr)/2;
        val=query(med);
        if(val==x)return med;
        else if(val<x) st=med+1;
        else dr=med-1;
    }
    return -1;
}
int main()
{
    int m,i,x,op,y;
    freopen("aib.in","r",stdin);
    freopen("aib.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(i=1; i<=n; i++)
    {
        scanf("%d",&x);
        upgrade(i,x);
    }
    for(i=1; i<=m; i++)
    {
        scanf("%d",&op);
        if(op==0)
        {
            scanf("%d%d",&x,&y);
            upgrade(x,y);
        }
        else if(op==1)
        {
            scanf("%d%d",&x,&y);
            printf("%d\n",query(y)-query(x-1));
        }else
        {
            scanf("%d",&x);
            printf("%d\n",caut(x));
        }
    }
    return 0;
}