#include <fstream>
#define IN "aib.in"
#define OUT "aib.out"
#define DMAX 100001
#define PUTERI 17
using namespace std;

ifstream fin(IN);
ofstream fout(OUT);

int n, m;
int v[DMAX];
int f[DMAX];
int p[18]={1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072};

void citire();
int suma(int);
void update(int, int);
int p2mare(int);
int poz_suma(int);//pozitia minima cu suma x

int main(int argc, const char * argv[]){
    citire();
    return 0;
}

int poz_suma(int x){
    int i;
    for (i=1; i<=n; ++i)
        if (suma(i)==x)
            return i;
    return 0;
}

int suma(int p){
    int sum=0, aux;
    for (aux=p; aux>0; aux-=p2mare(aux))
        sum+=f[aux];
    
    return sum;
}

void update(int p, int val){
    int aux;
    for (aux=p; aux<=n; aux+=p2mare(aux))
        f[aux]+=val;
}

int p2mare(int x){
    int i;
    for (i=PUTERI; i>=0; --i)
        if (x%p[i]==0)
            return p[i];
    return 0;
}

void citire(){
    fin >>n>>m;
    
    int i;
    for (i=1; i<=n; ++i){
        fin >>v[i];
        update(i, v[i]);
    }
    
    int x, y, tip;
    for (i=1; i<=m; ++i){
        fin >>tip;
        switch (tip) {
            case 0:
                fin >>x>>y;
                update(x, y);
                break;
            case 1:
                fin >>x>>y;
                fout <<suma(y)-suma(x-1)<<'\n';
                break;
            case 2:
                fin >>x;
                fout <<poz_suma(x)<<'\n';
                break;
        }
    }
}