#include<bits/stdc++.h>
#pragma GCC optimize ("Ofast")
using namespace std;
#define all(v) v.begin(), v.end()
#define pii pair<int, int>
#define F first
#define S second
typedef long long ll;
const int N=1e5+5;
int n, q, k, sz, c[N], mx[N];
ll sg[N];
void st(int x){
x+=sz-1;
sg[x]=c[x-sz+1];
while(x){
--x;
x/=2;
mx[x]=(c[mx[2*x+1]]<c[mx[2*x+2]]? mx[2*x+2] : mx[2*x+1]);
sg[x]=sg[2*x+1]+sg[2*x+2];
}
}
ll sum(int x, int lx, int rx, int l, int r){
if(lx>=r || rx<=l)
return 0;
if(lx>=l && rx<=r)
return sg[x];
int m=(lx+rx)/2;
return sum(2*x+1, lx, m, l, r)+sum(2*x+2, m, rx, l, r);
}
int seg(int x, int lx, int rx, int l, int r){
if(lx>=r || rx<=l)
return n;
if(lx>=l && rx<=r)
return mx[x];
int m=(lx+rx)/2;
int L=seg(2*x+1, lx, m, l, r), R=seg(2*x+2, m, rx, l, r);
return (c[L]<c[R] ? R : L);
}
void opr(int l, int r){
if(k==1)
return;
vector<pii>v;
int z=seg(0, 0, sz, l, r);
while(c[z]){
v.push_back({z, c[z]/k});
c[z]=0;
st(z);
z=seg(0, 0, sz, l, r);
}
for(auto u:v){
c[u.F]=u.S;
st(u.F);
}
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin>>n>>q>>k;
for(int i=0;i<n;++i){
cin>>c[i];
}
sz=1;
while(sz<n)
sz<<=1;
iota(mx+sz-1, mx+sz+n-1, 0);
for(int i=sz-1;i<sz+n-1;++i)
sg[i]=c[i-sz+1];
for(int i=sz-2;i>=0;--i){
sg[i]=sg[2*i+1]+sg[2*i+2];
mx[i]=(c[mx[2*i+1]]<c[mx[2*i+2]] ? mx[2*i+2] : mx[2*i+1]);
}
int s, t, u;
while(q--){
cin>>s>>t>>u;
if(s==1){
c[--t]=u;
st(t);
}
else if(s==2)
opr(--t, u);
else
cout<<sum(0, 0, sz, --t, u)<<'\n';
}
}
