#include <fstream>
#define UB(x) x&(-x)
using namespace std;
int i,j,N,m,n,w,a,b,cerinta;
int AIB[100003];
int suma(int poz, int val) {
    for(int i = poz; i <= n; i += UB(i))
        AIB[i] += val;
    return 0;
}
int query(int poz)
{
    int sumin = 0;
    for(int i = poz; i >= 1; i -= UB(i))
        sumin += AIB[i];
    return sumin;
}
int cautbin(int N)
{
    int st = 1, dr = n, mij = 0;
    while (st <= dr) {
        mij = (st + dr) / 2;
        if(N <= query(mij))
            dr = mij - 1;
        else                st = mij + 1;
    }
    return st;
}
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",&w); suma(i,w);
    }
    for(i=1;i<=m;i++)
    {
        scanf("%d",&cerinta);
        if(cerinta==0)
        {
            scanf("%d %d",&a,&b);
            suma(a,b);
        }
        else if(cerinta==1)
        {
            scanf("%d %d",&a,&b);
            printf("%d \n",query(b)-query(a-1));
        }
        else if(cerinta==2)
        {
            scanf("%d",&a);
            if(query(cautbin(a))!=a)
                printf("%d \n",-1);
            else printf("%d \n",cautbin(a));
        }
    }
    return 0;
}