#include <bits/stdc++.h>
#define len(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define ll long long
#define ld long double
#define i128 __int128_t
#define ff first
#define ss second
#define pii pair<int, int>
#define _cnt __builtin_popcount
#define debug(x) cerr << #x << " " << x << "\n";
// #define int ll
using namespace std;
const int maxn = 1e5 + 4, maxa = 5e6, inf = 2e9, maxp = 1234, mod = 1e9 + 7;
const ll infll = 1e18;
const double eps = 1e-9;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int N = 1 << (__lg(maxn) + 1);
int k;
struct Segtree {
int mn = 0, mx = 0, push = -1;
ll sum = 0;
int lb, rb;
Segtree *l, *r;
Segtree(int lb, int rb=N): lb(lb), rb(rb) {
if (lb == rb - 1) {
l = nullptr;
r = nullptr;
return;
}
int m = lb + rb >> 1;
l = new Segtree(lb, m);
r = new Segtree(m, rb);
}
void make_push() {
if (push == -1) {
return;
}
l->sum = 1LL * (l->rb - l->lb) * push;
l->mn = l->mx = l->push = push;
r->sum = 1LL * (r->rb - r->lb) * push;
r->mn = r->mx = r->push = push;
push = -1;
}
void upd_pt(int pos, int val) {
if (pos < lb || rb <= pos) {
return;
}
if (lb == pos && pos == rb - 1) {
sum = mn = mx = val;
return;
}
make_push();
l->upd_pt(pos, val);
r->upd_pt(pos, val);
sum = l->sum + r->sum;
mn = min(l->mn, r->mn);
mx = max(l->mx, r->mx);
}
void _upd_rng(int ql, int qr) {
if (qr <= lb || rb <= ql || mx == 0 || k == 1) {
return;
}
if (ql <= lb && rb <= qr && mn / k == mx / k) {
int val = mn / k;
sum = 1LL * val * (rb - lb);
mn = mx = val;
push = val;
return;
}
make_push();
l->_upd_rng(ql, qr);
r->_upd_rng(ql, qr);
sum = l->sum + r->sum;
mn = min(l->mn, r->mn);
mx = max(l->mx, r->mx);
}
ll _get(int ql, int qr) {
if (qr <= lb || rb <= ql) {
return 0;
}
if (ql <= lb && rb <= qr) {
return sum;
}
make_push();
return l->_get(ql, qr) + r->_get(ql, qr);
}
ll get(int ql, int qr) {
return _get(ql, qr + 1);
}
void upd_rng(int ql, int qr) {
_upd_rng(ql, qr + 1);
}
};
void solve() {
int n, q;
cin >> n >> q >> k;
vector<int> v(n);
for (int &i : v) {
cin >> i;
}
Segtree st(0, N);
for (int i = 0; i < n; i++) {
st.upd_pt(i, v[i]);
}
while (q--) {
int type;
cin >> type;
if (type == 1) {
int pos, val;
cin >> pos >> val;
--pos;
st.upd_pt(pos, val);
} else if (type == 2) {
int ql, qr;
cin >> ql >> qr;
--ql, --qr;
st.upd_rng(ql, qr);
} else {
int ql, qr;
cin >> ql >> qr;
--ql, --qr;
cout << st.get(ql, qr) << "\n";
}
}
}
int32_t main() {
cin.tie(nullptr)->sync_with_stdio(false);
int t = 1;
// cin >> t;
while (t--)
solve();
}
