#include <cstdio>
# define zero(x) (x&(-x))
using namespace std;
int aib[100001],n,m;
void update(int poz, int val)
{
    int i;
    for(i=poz; i<=n; i+=zero(i))
        aib[i]+=val;
}
int suma(int poz)
{
    int i,r=0;
    for(i=poz; i>0; i-=zero(i))
        r+=aib[i];
    return r;
}
int cautbin(int k)
{
    int st,dr,m,sol;
    st=1; dr=n;
    while(st<=dr)
    {
        m=(st+dr)/2;
        sol=suma(m);
        if(sol==k) return m;
        if(sol<k) 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", &n, &m);
    int x,a,val,poz,i,b,k,op;
    for(i=1; i<=n; ++i)
    {
        scanf("%d ", &x);
        update(i,x);
    }
    for(i=1; i<=m; ++i)
    {
        scanf("%d ", &op);
        if(op==0)
        {
            scanf("%d %d\n", &poz, &val);
            update(poz,val);
        }
        if(op==1)
        {
            scanf("%d %d\n", &a, &b);
            printf("%d\n", suma(b)-suma(a-1));
        }
        if(op==2)
        {
            scanf("%d\n", &k);
            printf("%d\n", cautbin(k));
        }
    }
    return 0;
}