#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};
}
}
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, k = 1;
for (int j = 0; 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);
}
};
struct St {
vector<ll> st;
St() : st(n << 1) {}
void update(int i, int v) {
for (st[i += n] = v; i >>= 1;) st[i] = st[i << 1] + st[i << 1 | 1];
}
ll query(int l, int r) {
ll ret = 0;
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if (l & 1) ret += st[l++];
if (r & 1) ret += st[--r];
}
return ret;
}
};
int main() {
cin >> n >> q >> K;
if (K > 1) {
Node root{1, n};
for (int i = 1; i <= n; ++i) {
int x;
cin >> x;
root.update(1, n, i, x);
}
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;
}
} else {
St st;
for (int i = 0; i < n; ++i) {
int x;
cin >> x;
st.update(i, x);
}
while (q--) {
int s, t, u;
cin >> s >> t >> u;
if (s == 1) st.update(t - 1, u);
else if (s == 3) cout << st.query(t - 1, u) << endl;
}
}
}
