#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 1000000007;
const char nl = '\n';
const int MX = 100001;
int arr[MX];
struct node{
int soma, mx;
node operator+(node aux){
return {soma+aux.soma,max(mx,aux.mx)};
}
};
node seg[4*MX];
int potencias[30];
int k;
void build(int pos, int ini, int fim){
if(ini==fim){
seg[pos]={arr[ini],arr[ini]};
return;
}
int m=(ini+fim)/2;
int e=2*pos,d=2*pos+1;
build(e,ini,m);
build(d,m+1,fim);
seg[pos]=seg[e]+seg[d];
}
void updt1(int pos, int ini, int fim, int id, int val){
if(ini>id || fim<id)return;
if(ini==fim){
seg[pos]={val,val};
return;
}
int m=(ini+fim)/2;
int e=2*pos,d=2*pos+1;
updt1(e,ini,m,id,val);
updt1(d,m+1,fim,id,val);
seg[pos]=seg[e]+seg[d];
}
void spray(int pos,int ini, int fim, int l, int r){
if(ini>r || fim<l)return;
if(l<=ini && fim<=r){
seg[pos].mx/=k;
if(seg[pos].mx==0){
seg[pos].soma=0;
return;
}
else if(ini==fim){
seg[pos].soma=seg[pos].mx;
return;
}
}
int m=(ini+fim)/2;
int e=2*pos,d=2*pos+1;
spray(e,ini,m,l,r);
spray(d,m+1,fim,l,r);
seg[pos]=seg[e]+seg[d];
}
int query(int pos, int ini, int fim, int l, int r){
if(ini>r || fim<l)return 0;
if(l<=ini && fim<=r){
return seg[pos].soma;
}
int m=(ini+fim)/2;
int e=2*pos,d=2*pos+1;
return query(e,ini,m,l,r)+query(d,m+1,fim,l,r);
}
void solve() {
int n,q;
cin>>n>>q>>k;
for(int i=1;i<=n;i++){
cin>>arr[i];
}
build(1,1,n);
while(q--){
int tipo,a,b;
cin>>tipo>>a>>b;
if(tipo==1){
updt1(1,1,n,a,b);
}
else if(tipo==2){
if(k==1)continue;
spray(1,1,n,a,b);
}
else{
cout<<query(1,1,n,a,b)<<endl;
}
}
}
int32_t main() {
cin.tie(0)->sync_with_stdio(0);
cin.exceptions(cin.failbit);
int T = 1;
// cin >> T;
while(T--) {
solve();
}
return 0;
}
