#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define int long long
#define double long double
#define x first
#define y second
#define pb push_back
using namespace std;
using namespace __gnu_pbds;
using pii=pair <int,int>;
using tii=pair <pii,int>;
int n,k;
int a[400040],mn[400040],mx[400040],sum[400040],laz[400040],pw[400040];
void pushup(int id){
mn[id]=min(mn[2*id],mn[2*id+1]);
mx[id]=max(mx[2*id],mx[2*id+1]);
sum[id]=sum[2*id]+sum[2*id+1];
}
void pushdown(int id,int tl,int tr){
if (!laz[id]) return;
int tm=(tl+tr)/2;
mn[2*id]/=pw[laz[id]]; mn[2*id+1]/=pw[laz[id]];
mx[2*id]/=pw[laz[id]]; mx[2*id+1]/=pw[laz[id]];
sum[2*id]=(tm-tl+1)*mn[2*id]; sum[2*id+1]=(tr-tm)*mn[2*id+1];
laz[2*id]+=laz[id]; laz[2*id+1]+=laz[id];
laz[id]=0;
}
void build(int id,int tl,int tr){
if (tl==tr){
mn[id]=a[tl]; mx[id]=a[tl]; sum[id]=a[tl];
return;
}
int tm=(tl+tr)/2;
build(2*id,tl,tm);
build(2*id+1,tm+1,tr);
pushup(id);
}
void update1(int id,int tl,int tr,int pos,int val){
if (tl==tr){
mn[id]=val; mx[id]=val; sum[id]=val;
return;
}
pushdown(id,tl,tr);
int tm=(tl+tr)/2;
if (pos<=tm) update1(2*id,tl,tm,pos,val);
else update1(2*id+1,tm+1,tr,pos,val);
pushup(id);
}
void update2(int id,int tl,int tr,int l,int r){
if (l>r) return;
if (l<=tl&&tr<=r&&mn[id]/k==mx[id]/k){
mn[id]/=k;
mx[id]/=k;
sum[id]=(tr-tl+1)*mn[id];
laz[id]++;
return;
}
pushdown(id,tl,tr);
int tm=(tl+tr)/2;
update2(2*id,tl,tm,l,min(r,tm));
update2(2*id+1,tm+1,tr,max(l,tm+1),r);
pushup(id);
}
int query(int id,int tl,int tr,int l,int r){
if (l>r) return 0;
if (l<=tl&&tr<=r) return sum[id];
pushdown(id,tl,tr);
int tm=(tl+tr)/2;
int lx=query(2*id,tl,tm,l,min(r,tm));
int rx=query(2*id+1,tm+1,tr,max(l,tm+1),r);
return lx+rx;
}
void solve(){
int q;
cin>>n>>q>>k;
if (k>=2){
pw[0]=1;
for (int i=1; i<=q; i++){
if (pw[i-1]>2e15/k) pw[i]=0;
else pw[i]=pw[i-1]*k;
}
}
for (int i=1; i<=n; i++) cin>>a[i];
build(1,1,n);
while (q--){
int type,l,r; cin>>type>>l>>r;
if (type==1) update1(1,1,n,l,r);
else if (type==2&&k>1) update2(1,1,n,l,r);
else if (type==3){
int tp=query(1,1,n,l,r);
cout<<tp<<'\n';
}
}
}
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0);
int t=1;
//cin>>t;
while (t--) solve();
}
