#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
const int N = 1e5 + 5, LG = 30;
int n, q, k;
int lz[4 * N];
long long s[4 * N][LG];
void pull(int id) {
for (int j = 0; j < (k > 1 ? LG : 1); ++j) {
s[id][j] = s[id * 2][j] + s[id * 2 + 1][j];
}
}
void app(int id, int x) {
x = min(x, LG);
if (x == LG) {
fill(s[id], s[id] + LG, 0);
} else {
for (int i = 0; i + x < LG; ++i) {
s[id][i] = s[id][i + x];
s[id][i + x] = 0;
}
}
lz[id] += x;
}
void psh(int id) {
if (lz[id]) {
app(id * 2, lz[id]);
app(id * 2 + 1, lz[id]);
lz[id] = 0;
}
}
void upd(int i, int x, int id = 1, int l = 1, int r = n) {
if (l == r) {
s[id][0] = x;
if (k > 1) {
for (int i = 1; i < LG; ++i) {
x /= k;
s[id][i] = x;
}
}
return;
}
psh(id);
int md = (l + r) / 2;
if (i <= md) {
upd(i, x, id * 2, l, md);
} else {
upd(i, x, id * 2 + 1, md + 1, r);
}
pull(id);
}
void spray(int u, int v, int id = 1, int l = 1, int r = n) {
if (u <= l && r <= v) {
app(id, 1);
return;
}
psh(id);
int md = (l + r) / 2;
if (u <= md) {
spray(u, v, id * 2, l, md);
}
if (md < v) {
spray(u, v, id * 2 + 1, md + 1, r);
}
pull(id);
}
long long qry(int u, int v, int id = 1, int l = 1, int r = n) {
if (u <= l && r <= v) {
return s[id][0];
}
psh(id);
int md = (l + r) / 2;
if (v <= md) {
return qry(u, v, id * 2, l, md);
}
if (md < u) {
return qry(u, v, id * 2 + 1, md + 1, r);
}
return qry(u, v, id * 2, l, md) + qry(u, v, id * 2 + 1, md + 1, r);
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> q >> k;
for (int i = 1; i <= n; ++i) {
int x; cin >> x;
upd(i, x);
}
while (q--) {
int type, a, b; cin >> type >> a >> b;
if (type == 1) {
upd(a, b);
} else if (type == 2) {
if (k > 1) {
spray(a, b, 1);
}
} else {
cout << qry(a, b) << "\n";
}
}
return 0;
}
