#include <cstdio>

using namespace std;

const int nmax=100000;
int n;
int aib[nmax+1];

inline int lsb(int x)
{
    return x&-x;
}

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

int querry(int pos)
{
    int ans = 0;
    for(int i=pos; i>0; i-=lsb(i))
        ans += aib[i];
    return ans;
}

int binary(int pos)
{
    int ans=0, sc=0;
    for(int k=1<<15;k>0;k>>=1)
        if(ans+k<=n && sc+aib[ans+k]<=pos)
        {
            ans+=k;
            sc+=aib[ans];
        }
    if(sc!=pos || ans==0)
        return -1;
    return ans;
}
int main()
{
    freopen("aib.in", "r", stdin);
    freopen("aib.out", "w", stdout);
    int m;
    scanf("%d%d", &n, &m);
    for(int i=0; i<n; i++)
    {
        int x;
        scanf("%d", &x);
        update(i+1, x);
    }
    int x, y;
    for(int i=0;i<m;i++)
    {
        int t;
        scanf("%d", &t);
        if(t==0)
        {
            scanf("%d%d", &x, &y);
            update(x, y);
        }
        else if(t==1)
        {
            scanf("%d%d", &x, &y);
            printf("%d\n", querry(y) - querry(x-1));
        }
        else if(t==2)
        {
            scanf("%d", &x);
            printf("%d\n", binary(x));
        }
    }
    return 0;
}