#include <bits/stdc++.h>

using namespace std;
//ifstream f("aib.in");
//ofstream g("aib.out");
const int N = 100010;
const int buffSize = 100000;
char buff[buffSize+10];
int pb=0;
void inc()
{
    pb++;
    if(pb==buffSize)
    {
        pb=0;
        fread(buff,1,buffSize,stdin);
    }
}
void readInt(int &x)
{
    while(buff[pb]<'0'||buff[pb]>'9')inc();
    x=0;
    while(buff[pb]>='0'&&buff[pb]<='9')
    {
        x=10*x+buff[pb]-'0';
        inc();
    }
}
int n,o,t,a,b,A[N];
inline void aduna(int,int);
inline int suma(int);
int main()
{
    freopen("aib.in","r",stdin);
    freopen("aib.out","w",stdout);
    readInt(n);
    readInt(o);
    for(int i=1; i<=n; i++)
    {
        readInt(a);
        aduna(i,a);
    }
    for(; o; o--)
    {
        readInt(t);
        readInt(a);
        if(t==0)
        {
            readInt(b);
            aduna(a,b);
        }
        else if(t==1)
        {
            readInt(b);
            printf("%d\n",suma(b)-suma(a-1));
        }
        else
        {
            int lo=0,hi=n,mi;
            while(hi-lo>1)
            {
                mi=(lo+hi)/2;
                if(suma(mi)>=a)
                    hi=mi;
                else
                    lo=mi;
            }
            if(suma(hi)==a)
                printf("%d\n",hi);
            else
                printf("-1\n");

        }

    }
    return 0;
}
inline void aduna(int poz,int val)
{
    for(; poz<=n; poz+=(poz&(-poz)))
        A[poz]+=val;
}
inline int suma(int poz)
{
    int sum=0;
    for(; poz>0; poz-=(poz&(-poz)))
        sum+=A[poz];
    return sum;
}