#include <cstdio>
#define lb(x) x&(-x)
#define nmax 100100

using namespace std;

int aib[nmax];
int i, n, m, x, y, pos, value, s, type;

void update(int value, int pos)
{
    for(int i=pos; i<=n; i+=lb(i))
        aib[i]+=value;
}

inline int sum(int pos)
{
    int sum=0;
    for(int i=pos; i>=1; i-=lb(i))
        sum+=aib[i];

    return sum;
}

inline int qsum(int s)
{
    int l=1, r=n, mid, v;

    while(l<=r)
    {
        mid=(l+r)>>1;

        v=sum(mid);

        if(v==s) return mid;
        else if(s<v) r=mid-1;
            else l=mid+1;
    }
    return -1;
}
int main()
{
    freopen("aib.in", "rt", stdin);
    freopen("aib.out", "wt", stdout);

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

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

    for(i=1; i<=m; ++i)
    {
        scanf("%d", &type);
        if(type==0)
        {
            scanf("%d%d", &pos, &value);
            update(value, pos);
        }
        if(type==1)
        {
            scanf("%d%d", &x, &y);
            printf("%d\n", sum(y)-sum(x-1));
        }
        if(type==2)
        {
            scanf("%d", &x);
            printf("%d\n", qsum(x));
        }
    }
    return 0;
}