#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
#define ar array
const int INF = 1e17;
const int MOD = 1e9;
struct SegTree {
vector<deque<int>> values;
vector<int> operations;
int size, k;
void init(int n, int _k) {
size = 1; k = _k;
while (size < n) size <<= 1;
operations.resize(2*size);
values.resize(2*size);
}
void propogate(int x, int lx, int rx) {
if (rx - lx != 1) {
operations[2*x+1] += operations[x];
operations[2*x+2] += operations[x];
}
for ( ; operations[x] && values[x].size() > 1; operations[x]--) values[x].pop_front();
operations[x] = 0;
}
void update(int x, int lx, int rx) {
if (rx - lx == 1) return;
int m = (lx + rx) >> 1;
while (values[x].size() > 0) values[x].pop_front();
propogate(2*x+1, lx, m);
propogate(2*x+2, m, rx);
int i, j;
for (i = 0, j = 0; i < values[2*x+1].size() && j < values[2*x+2].size(); ++i, ++j) {
values[x].push_back(values[2*x+1][i] + values[2*x+2][j]);
}
for (; i < values[2*x+1].size(); ++i) values[x].push_back(values[2*x+1][i]);
for (; j < values[2*x+2].size(); ++j) values[x].push_back(values[2*x+2][j]);
}
void set(int i, int v, int x, int lx, int rx) {
propogate(x, lx, rx);
if (rx - lx == 1) {
while (values[x].size() > 0) values[x].pop_front();
while (v && k > 1) {
values[x].push_back(v); v /= k;
}
values[x].push_back(v);
return;
}
int m = (lx + rx) >> 1;
if (i < m) set(i, v, 2*x+1, lx, m);
else set(i, v, 2*x+2, m, rx);
update(x, lx, rx);
}
void set(int i, int v) {
set(i, v, 0, 0, size);
}
void modify(int l, int r, int x, int lx, int rx) {
propogate(x, lx, rx);
if (lx >= r || l >= rx) return;
if (l <= lx && rx <= r) return void(operations[x]++);
int m = (lx + rx) >> 1;
modify(l, r, 2*x+1, lx, m);
modify(l, r, 2*x+2, m, rx);
update(x, lx, rx);
}
void modify(int l, int r) {
modify(l, r, 0, 0, size);
}
int calc(int l, int r, int x, int lx, int rx) {
propogate(x, lx, rx);
if (lx >= r || l >= rx) return 0;
if (l <= lx && rx <= r) {
return values[x].front();
}
int m = (lx + rx) >> 1;
int s1 = calc(l, r, 2*x+1, lx, m);
int s2 = calc(l, r, 2*x+2, m, rx);
return s1 + s2;
}
int calc(int l, int r) {
return calc(l, r, 0, 0, size);
}
};
int32_t main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, m, k; cin>>n>>m>>k;
SegTree st; st.init(n, k);
for (int i = 0; i < n; i++) {
int x; cin>>x;
st.set(i, x);
}
while (m--) {
int t, a, b; cin>>t>>a>>b;
if (t == 1) {
st.set(a-1, b);
} else if (t == 2 && k > 1) {
st.modify(a-1, b);
} else if (t == 3) {
cout<<st.calc(a-1, b)<<"\n";
}
}
}
