#include <fstream>
#define zeros(x) x&(-x)
#define nmax 100004
#define LIM (1<<20)
#define verifica ++poz == LIM ? in.read(my_text,LIM),poz=0 : 0

using namespace std;

ifstream in("aib.in");
ofstream out("aib.out");

int N,M,AIB[nmax],step;

/*****************/

char my_text[LIM];
int poz ;
inline void Citeste(int &nr)
{
    if(my_text[0]=='\0')in.read(my_text,LIM);
    else for(;my_text[poz]<'0'||my_text[poz]>'9';verifica);
    for(nr=0;my_text[poz]>='0'&&my_text[poz]<='9';nr=nr*10+my_text[poz]-'0',verifica);
}


/*****************/

inline void Update(int p,int val)
{
    for(;p<=N;p+=zeros(p))
        AIB[p]+=val;
}

inline int Query(int p)
{
    int S = 0;
    for(;p;p-=zeros(p))
        S+=AIB[p];
    return S;
}

inline int BSearch(int key)
{
    if(key==0)
        return -1;
    int i,st;
    for(st=step,i=0;st;st>>=1)
        if(i+st<=N)
        {
            if(AIB[i+st]<=key)
                key-=AIB[i+st],i+=st;
            if(key==0)
                return i;
        }
    return -1;
}

int main()
{
    int i,x,a,b,op;
    Citeste(N);
    Citeste(M);
    for(i=1;i<=N;i++)
        Citeste(x),Update(i,x);

    for(step=1;step<N;step<<=1);//pentru cautare binara

    while(M--)
    {
        Citeste(op);
        if(op==0)
        {
            Citeste(a);
            Citeste(b);
            Update(a,b);
        }
        if(op==1)
        {
            Citeste(a);
            Citeste(b);
            out<<Query(b)-Query(a-1)<<'\n';
        }
        if(op==2)
        {
            Citeste(a);
            out<<BSearch(a)<<'\n';
        }
    }
    return 0;
}