// Born_To_Laugh - Hughie Do
#include <bits/stdc++.h>
#define alle(AC) AC.begin(), AC.end()
#define fi first
#define se second
using namespace std;
typedef long long ll;
[[maybe_unused]] const int MOD = 998244353, INF = 1e9 + 7;
const int maxn = 1e5 + 10;
int n, q, k;
int c[maxn];
class SegTree
{
private:
int n;
vector<int> lazy;
vector<deque<pair<int, int>>> tree;
void ope(int id, int l, int r){
if(lazy[id] == 0) return;
for(int i=1; i<=min(32, lazy[id]); ++i){
tree[id].pop_front();
tree[id].push_back({0, 0});
}
if(l != r){
lazy[id << 1] += lazy[id];
lazy[id << 1|1] += lazy[id];
}
lazy[id] = 0;
}
void build(int id, int l, int r){
if(l == r){
int x = c[l];
tree[id].clear();
for(int i=0; i<32; ++i){
tree[id].push_back({x - (x % k), x % k});
x /= k;
}
return;
}
int mid = (l + r) >> 1;
build(id << 1, l, mid);
build(id << 1|1, mid + 1, r);
tree[id].clear();
for(int i=0; i<32; ++i){
tree[id].push_back({tree[id << 1][i].fi + tree[id << 1|1][i].fi,
tree[id << 1][i].se + tree[id << 1|1][i].se});
}
}
void upd(int id, int l, int r, int pos, int val){
ope(id, l, r);
if(pos < l || pos > r) return;
if(l == r){
int x = val;
tree[id].clear();
for(int i=0; i<32; ++i){
tree[id].push_back({x - (x % k), x % k});
x /= k;
}
return;
}
int mid = (l + r) >> 1;
upd(id << 1, l, mid, pos, val);
upd(id << 1|1, mid + 1, r, pos, val);
tree[id].clear();
for(int i=0; i<32; ++i){
tree[id].push_back({tree[id << 1][i].fi + tree[id << 1|1][i].fi,
tree[id << 1][i].se + tree[id << 1|1][i].se});
}
}
void rangeupd(int id, int l, int r, int lo, int hi){
ope(id, l, r);
if(l > hi || r < lo) return;
else if(l >= lo && r <= hi){
lazy[id]++;
ope(id, l, r);
return;
}
int mid = (l + r) >> 1;
rangeupd(id << 1, l, mid, lo, hi);
rangeupd(id << 1|1, mid + 1, r, lo, hi);
tree[id].clear();
for(int i=0; i<32; ++i){
tree[id].push_back({tree[id << 1][i].fi + tree[id << 1|1][i].fi,
tree[id << 1][i].se + tree[id << 1|1][i].se});
}
}
ll qr(int id, int l, int r, int lo, int hi){
ope(id, l, r);
if(l > hi || r < lo) return 0;
else if(l >= lo && r <= hi) return tree[id].front().fi + tree[id].front().se;
int mid = (l + r) >> 1;
return qr(id << 1, l, mid, lo, hi) + qr(id << 1|1, mid + 1, r, lo, hi);
}
public:
void init(int len){
n = len;
tree.assign(n << 2, {});
lazy.assign(n << 2, 0);
build(1, 1, n);
}
void upd(int pos, int val){
upd(1, 1, n, pos, val);
}
void rangeupd(int l, int r){
rangeupd(1, 1, n, l, r);
}
ll qr(int l, int r){
return qr(1, 1, n, l, r);
}
};
SegTree st;
void solve(){
cin >> n >> q >> k;
for(int i=1; i<=n; ++i) cin >> c[i];
st.init(n);
while(q--){
int t;cin >> t;
if(t == 1){
int a, b;cin >> a >> b;
st.upd(a, b);
}
else if(t == 2){
int a, b;cin >> a >> b;
st.rangeupd(a, b);
}
else{
int a, b;cin >> a >> b;
cout << st.qr(a, b) << '\n';
}
}
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
solve();
}
