#include <fstream>
#define ub(x) (x&(-x))
using namespace std;
ifstream f ("aib.in");
ofstream g ("aib.out");
int i,N,aib[100002],m,c,x,y,st,dr,poz,t,j;
void update (int poz, int val)
{
    for (i=poz;i<=N;i+=ub(i))
        aib[i]+=val;
}
int Sum(int poz)
{
    int S = 0;
    for (i=poz;i>0;i-=ub(i))
        S+=aib[i];
    return S;
}
int main()
{
    f>>N>>m;
    for (j=1;j<=N;j++)
    {
        f>>x;
        update (j,x);
    }
    for (j=1;j<=m;j++) {
        f>>c;
        if (c==0) {
            f>>x>>y;
            update(x,y);
        }
        else if (c==1) {
            f>>x>>y;
            g<<Sum(y)-Sum(x-1)<<'\n';
        }
        else if (c==2) {
            f>>x;
            st=1;
            dr=N;
            poz=-1;
            t = 0;
            while (st<=dr && poz == -1) {
                t=(st+dr)/2;
                if (Sum(t)==x) poz=t;
                else if (Sum(t)>x) dr=t-1;
                else st=t+1;
            }
            g<<poz<<'\n';
        }
    }
}