#include <fstream>

#define LSB(x) ((-x)&x)
#define X1 100001

using namespace std;

int N;
int v[X1];

inline void update(int n,int val)
{
    while(n<=N)
    {
        v[n]+=val;
        n+=LSB(n);
    }
}

inline int query(int x)
{
    int sum=0;

    while(x>0)
    {
        sum+=v[x];
        x-=LSB(x);
    }

    return sum;
}

inline int BS(int x,int L,int R)
{
    if(L<=R)
    {
        int M=L+(R-L)/2;
        int val=query(M);

        if(val<x) return BS(x,M+1,R);
        else
        if(val>x) return BS(x,L,M-1);
        else return M;
    }
    else return -1;
}

ifstream in;
ofstream out;

int main()
{
    int M,x,tip,a,b;

    in.open("aib.in");
    in>>N>>M;
    for(int i=1;i<=N;++i)
    {
        in>>x;
        update(i,x);
    }

    out.open("aib.out");
    for(;M;--M)
    {
        in>>tip;
        if(tip==0)
        {
            in>>a>>b;
            update(a,b);
        }
        else
        if(tip==1)
        {
            in>>a>>b;
            out<<query(b)-query(a-1)<<'\n';
        }
        else
        {
            in>>a;
            out<<BS(a,1,N)<<'\n';
        }
    }
    in.close();
    out.close();

    return 0;
}