#include <bits/stdc++.h>

using namespace std;

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

const int N=100010;
int n,m,aib[N];

void update(int ,int );
int sum(int );
int aib_search(int ,int ,int );

int main()
{
    inf>>n>>m;
    for(int i=1; i<=n; i++)
    {
        int x;
        inf>>x;
        update(x,i);
    }
    int p, a, b;
    for(int i=1; i<=m; i++)
    {
        inf>>p;
        if(p==0)
            {inf>>a>>b;update(b,a);}
        else if(p==1)
        {
            inf>>a>>b;
            if(a==1)
                outf<<sum(b)<<'\n';
            else
                outf<<sum(b)-sum(a-1)<<'\n';
        }
        else
        {
            inf>>a;
            outf<<aib_search(1,n,a)<<'\n';
        }
    }

    return 0;
}

void update(int val, int poz)
{
    for(int i=poz; i<=n; i+=(i&(-i)))
        aib[i]+=val;
}

int sum(int poz)
{
    int ret=0;
    for(int i=poz; i>0; i-=(i&(-i)))
        ret+=aib[i];
    return ret;
}

int aib_search(int st, int dr, int val)
{
    if(st>dr)
        return -1;
    int m=(st+dr)/2, q=sum(m);
    if(q==val)
    {
        int aux=aib_search(st,m-1,val);
        if(aux>0)
            return aux;
        else
            return m;
    }
    else
    {
        if(q>val)
            return aib_search(st, m-1, val);
        else
            return aib_search(m+1, dr, val);
    }
}