#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll n, q, k;
map<int,ll> mp;
ll tree[100005];
void update(int idx, int val) {
for (int i = idx; i < 100005; i += (i & -i)) tree[i] += val;
}
ll query(int idx) {
ll ans = 0;
for (int i = idx; i >= 1; i -= (i & -i)) ans += tree[i];
return ans;
}
int main() {
ios_base::sync_with_stdio(0), cin.tie(0);
cin >> n >> q >> k;
for (int i = 1; i <= n; i++) {
int x; cin >> x;
mp[i] = x;
update(i, x);
}
while (q--) {
int type, l, r;
cin >> type >> l >> r;
if (type == 1) {
update(l, r - mp[l]);
mp[l] = r;
} else if (type == 2) {
if (k == 1) continue;
auto it = mp.lower_bound(l);
for (; it != mp.end() && it->first <= r;) {
if (it->second < k) {
update(it->first, -it->second);
it = mp.erase(it);
continue;
}
ll diff = it->second/k - it->second;
it->second += diff;
update(it->first, diff);
it++;
}
} else {
cout << query(r) - query(l - 1) << "\n";
}
}
}
