#include <fstream>
#define nmax 100005
#define inf (1<<30) // sau 0x3f3f3f3f
#define LSB(x) ( (-x)&x )
using namespace std;

int n,m,i,Aib[nmax],tip,a,b,x;

inline void update(int val, int poz)
{
    for (int ii=poz;ii<=n;ii+=LSB(ii))
        Aib[ii]+=val;
}

inline int Suma(int poz)
{
    int suma=0;
    for (int ii=poz;ii>0;ii-=LSB(ii))
        suma+=Aib[ii];
    return suma;
}

inline int suma_interval(int a, int b)
{
    return (Suma(b)-Suma(a-1));
}

int main()
{
    ifstream f("aib.in");
    ofstream g("aib.out");
    f>>n>>m;
    for (i=1;i<=n;i++)
    {
        f>>x;
        update(x,i);
    }
    for (i=1;i<=m;i++)
    {
        f>>tip;
        if (tip==0)
        {
            f>>a>>b;
            update(b,a);
        }
        else if (tip==1)
        {
            f>>a>>b;
            g<<suma_interval(a,b)<<"\n";
        }
        else
        {
            f>>a;
            for (int ii=1;ii<=n;ii++)
                if (suma_interval(1,ii)==a)
                {
                    g<<ii<<"\n";
                    break;
                }
        }
    }
    return 0;
}