#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sp << " " <<
#define nl << "\n"
int n, q, k;
vector<int> init;
struct segtree{
int sz = 1;
vector<array<int, 31>> sums;
array<int, 31> ID = {};
vector<int> ops;
void pull(int x){
for(int i=0; i<31; ++i) sums[x][i] = sums[2*x+1][i] + sums[2*x+2][i];
shift(sums[x], ops[x]);
}
void shift(array<int, 31> &c, int y){
for(int i=0; i<31; ++i) c[i] = (i+y) < 31 ? c[i+y] : 0;
}
void push(int x){
if(x+1<sz){
ops[2*x+1] += ops[x];
shift(sums[2*x+1], ops[x]);
ops[2*x+2] += ops[x];
shift(sums[2*x+2], ops[x]);
ops[x] = 0;
pull(x);
}
}
segtree(){
while(sz < n) sz *= 2;
sums.assign(2*sz, ID);
ops.assign(2*sz, 0);
build(0, 0, sz);
}
void build(int x, int lx, int rx){
if(rx-lx==1){
if(lx>=n) return;
for(int i=0; i<31; ++i){
sums[x][i] = init[lx]%k;
init[lx] /= k;
}
return;
}
int mx = (lx+rx)/2;
build(2*x+1, lx, mx);
build(2*x+2, mx, rx);
pull(x);
}
void divide(int l, int r, int x, int lx, int rx){
push(x);
if(r<=lx or rx<=l) return;
if(l<=lx and rx<=r){
++ops[x];
shift(sums[x], 1);
return;
}
int mx = (lx+rx)/2;
divide(l, r, 2*x+1, lx, mx);
divide(l, r, 2*x+2, mx, rx);
pull(x);
}
void divide(int l, int r){ divide(l, r+1, 0, 0, sz); }
void set(int pos, int val, int x, int lx, int rx){
push(x);
if(rx-lx==1){
for(int i=0; i<31; ++i){
sums[x][i] = val%k;
val /= k;
}
ops[x] = 0;
return;
}
int mx = (lx+rx)/2;
if(pos<mx) set(pos, val, 2*x+1, lx, mx);
else set(pos, val, 2*x+2, mx, rx);
pull(x);
}
void set(int pos, int val){ set(pos, val, 0, 0, sz); }
array<int, 31> get(int l, int r, int x, int lx, int rx){
push(x);
if(r<=lx or rx<=l) return ID;
if(l<=lx and rx<=r) return sums[x];
int mx = (lx+rx)/2;
auto resL = get(l, r, 2*x+1, lx, mx), resR = get(l, r, 2*x+2, mx, rx);
for(int i=0; i<31; ++i) resL[i] += resR[i];
return resL;
}
int get(int l, int r){
auto arr = get(l, r+1, 0, 0, sz);
int res = 0;
for(int i=0, mul=1; i<31 and mul<(int)1e11; ++i, mul*=k) res += arr[i]*mul;
return res;
}
};
signed main(){
ios_base::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> q >> k;
init.resize(n);
for(int &i : init) cin >> i;
segtree st;
while(q--){
int s, t, u; cin >> s >> t >> u;
if(s==1){
st.set(t-1, u);
}else if(s==2){
st.divide(t-1, u-1);
}else{
cout << st.get(t-1, u-1) nl;
}
}
}
