#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, q, K;
struct Node {
int val[30]{}, lazy = 0;
Node *lc{}, *rc;
void pull() { for (int j = 30; j--;) val[j] = lc->val[j] + rc->val[j]; }
Node(int l, int r) {
if (l < r) {
int m = (l + r) >> 1;
lc = new Node{l, m};
rc = new Node{m + 1, r};
pull();
} else {
cin >> val[0];
for (int j = 1; j < 30; ++j) {
val[j] = val[j - 1] / K;
val[j - 1] %= K;
}
}
}
void push() {
for (int i = 0; i < 30; ++i) val[i] = i + lazy < 30 ? val[i + lazy] : 0;
if (lc) lc->lazy += lazy, rc->lazy += lazy;
lazy = 0;
}
void update(int l, int r, int i, int v) {
push();
if (i < l or i > r) return;
if (l == r) {
for (int j = 0; j < 30; v /= K) val[j++] = v % K;
return;
}
int m = (l + r) >> 1;
lc->update(l, m, i, v);
rc->update(m + 1, r, i, v);
pull();
}
void update(int l, int r, int ul, int ur, int v) {
push();
if (ul > r or ur < l) return;
if (l >= ul and r <= ur) {
lazy += v;
push();
return;
}
int m = (l + r) >> 1;
lc->update(l, m, ul, ur, v);
rc->update(m + 1, r, ul, ur, v);
pull();
}
ll query(int l, int r, int ql, int qr) {
if (ql > r or qr < l) return 0;
push();
if (l >= ql and r <= qr) {
ll ans = 0;
for (int j = 0, k = 1; j < 30; ++j, k *= K) ans += k * val[j];
return ans;
}
int m = (l + r) >> 1;
return lc->query(l, m, ql, qr) + rc->query(m + 1, r, ql, qr);
}
};
int main() {
cin >> n >> q >> K;
Node root{1, n};
while (q--) {
int s, t, u;
cin >> s >> t >> u;
if (s == 1) root.update(1, n, t, u);
else if (s == 2) root.update(1, n, t, u, 1);
else cout << root.query(1, n, t, u) << endl;
}
}
