#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Seg {
int n;
vector<ll> sum, mx;
vector<char> lz_zero; // 1 if whole node is zero
int K;
Seg(int n=0, int K=2): n(n), K(K) {
sum.assign(4*n+4, 0);
mx.assign(4*n+4, 0);
lz_zero.assign(4*n+4, 0);
}
void build(int node, int l, int r, const vector<ll>& a) {
lz_zero[node] = 0;
if (l==r) {
sum[node] = mx[node] = a[l];
return;
}
int m=(l+r)>>1;
build(node<<1, l, m, a);
build(node<<1|1, m+1, r, a);
pull(node);
}
void pull(int node) {
sum[node] = sum[node<<1] + sum[node<<1|1];
mx[node] = max(mx[node<<1], mx[node<<1|1]);
}
void apply_zero(int node) {
sum[node] = 0;
mx[node] = 0;
lz_zero[node] = 1;
}
void push(int node) {
if (lz_zero[node]) {
apply_zero(node<<1);
apply_zero(node<<1|1);
lz_zero[node] = 0;
}
}
// point assign: set index pos to value val
void point_set(int node, int l, int r, int pos, ll val) {
if (l==r) {
sum[node] = mx[node] = val;
lz_zero[node] = 0;
return;
}
push(node);
int m=(l+r)>>1;
if (pos<=m) point_set(node<<1, l, m, pos, val);
else point_set(node<<1|1, m+1, r, pos, val);
pull(node);
}
// range divide once by K on [L,R]
void range_divide(int node, int l, int r, int L, int R) {
if (L>r || R<l) return;
if (L<=l && r<=R) {
if (mx[node] == 0) return; // already zero
if (mx[node] < K) {
// every value < K -> after one division becomes 0
apply_zero(node);
return;
}
if (l==r) {
// leaf: divide directly
ll v = sum[node] / K;
sum[node] = mx[node] = v;
lz_zero[node] = (v==0);
return;
}
}
// partial or need to go deeper
push(node);
int m=(l+r)>>1;
range_divide(node<<1, l, m, L, R);
range_divide(node<<1|1, m+1, r, L, R);
pull(node);
}
ll range_sum(int node, int l, int r, int L, int R) {
if (L>r || R<l) return 0;
if (L<=l && r<=R) return sum[node];
push(node);
int m=(l+r)>>1;
return range_sum(node<<1, l, m, L, R) + range_sum(node<<1|1, m+1, r, L, R);
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, Q;
int K;
if (!(cin >> N >> Q >> K)) return 0;
vector<ll> a(N+1);
for (int i=1;i<=N;i++) cin >> a[i];
Seg seg(N, K);
seg.build(1,1,N,a);
for (int i=0;i<Q;i++) {
int S, T, U;
cin >> S >> T >> U;
if (S==1) {
// assign: C[T] = U
seg.point_set(1,1,N,T, (ll)U);
} else if (S==2) {
// range divide once by K on [T,U]
if (K==1) {
// division by 1 does nothing
continue;
}
seg.range_divide(1,1,N,T,U);
} else if (S==3) {
// query sum
cout << seg.range_sum(1,1,N,T,U) << '\n';
}
}
return 0;
}
