#include <bits/stdc++.h>
using namespace std;
int N, Q, K;
vector<int> C(131072 + 1);
template<typename val>
struct PetriDish {
val c;
int i;
vector<val> ith_division = vector<val>(65);
void build (val _c) {
c = _c;
i = 0;
ith_division[0] = c / K;
for (int j = 1; j < 65; j++) {
ith_division[j] = ith_division[j - 1] / K;
}
}
val divide(int count) {
if (K == 1) {
return c;
}
i = count;
i--;
if (64 < i) {
return 0;
}
c = ith_division[i];
return ith_division[i];
}
};
PetriDish<int64_t> join(PetriDish<int64_t> i, PetriDish<int64_t> j) {
int64_t c = i.c + j.c;
vector<int64_t> ith_division(65);
for (int x = i.i, y = j.i, k = 0; k < 65; k++) {
ith_division[k] = i.divide(x + 1 + k) + j.divide(y + 1 + k);
}
PetriDish<int64_t> ans;
ans.c = c;
ans.i = 0;
ans.ith_division = ith_division;
return ans;
}
PetriDish<int64_t> ST[4 * (1 << 17) + 1];
bool lazy_flag[4 * (1 << 17) + 1];
int lazy_count[4 * (1 << 17) + 1];
void execute_lazy (int tree_index, int l, int r);
void set_lazy (int tree_index, int l, int r);
void build(int tree_index, int l, int r) {
if (l == r) {
ST[tree_index].build(C[l]);
return;
}
int mid = (l + r) / 2;
build(2 * tree_index, l, mid);
build(2 * tree_index + 1, mid + 1, r);
ST[tree_index] = join(ST[2 * tree_index], ST[2 * tree_index + 1]);
}
void execute_lazy (int tree_index, int l, int r) {
if (lazy_flag[tree_index] == false) {
return;
}
if (l == r) {
return;
}
// cout << l << ' ' << r << '\n';
int mid = (l + r) / 2;
lazy_count[2 * tree_index] += lazy_count[tree_index];
lazy_count[2 * tree_index + 1] += lazy_count[tree_index];
lazy_count[tree_index] = 0;
set_lazy(2 * tree_index, l, mid);
set_lazy(2 * tree_index + 1, mid + 1, r);
lazy_flag[tree_index] = false;
ST[tree_index] = ST[tree_index] = join(ST[2 * tree_index], ST[2 * tree_index + 1]);
}
void set_lazy (int tree_index, int l, int r) {
// cout << "Info: " << lazy_count[tree_index] << '\n';
ST[tree_index].divide(lazy_count[tree_index]);
if (l == r) {
return;
}
lazy_flag[tree_index] = true;
}
void spray(int tree_index, int l, int r, int l_target, int r_target) {
if (r < l_target || r_target < l) {
return;
}
if (l_target <= l && r <= r_target) {
lazy_count[tree_index]++;
set_lazy(tree_index, l, r);
// cout << "Lazy_count: " << ST[tree_index].c << ' ' << l << ' ' << r << '\n';
return;
}
execute_lazy(tree_index, l, r);
int mid = (l + r) / 2;
spray(2 * tree_index, l, mid, l_target, r_target);
spray(2 * tree_index + 1, mid + 1, r, l_target, r_target);
ST[tree_index] = join(ST[2 * tree_index], ST[2 * tree_index + 1]);
}
void edit(int tree_index, int l, int r, int target, int payload) {
if (l == target && r == target) {
ST[tree_index].build(payload);
lazy_count[tree_index] = 0;
return;
}
if (r < target || target < l) {
return;
}
execute_lazy(tree_index, l, r);
int mid = (l + r) / 2;
edit(2 * tree_index, l, mid, target, payload);
edit(2 * tree_index + 1, mid + 1, r, target, payload);
ST[tree_index] = ST[tree_index] = join(ST[2 * tree_index], ST[2 * tree_index + 1]);
}
int64_t query(int tree_index, int l, int r, int l_target, int r_target) {
if (r < l_target || r_target < l) {
return 0;
}
if (l_target <= l && r <= r_target) {
// cout << "Range " << l << ' ' << r << ": " << ST[tree_index].c << '\n';
return ST[tree_index].c;
}
execute_lazy(tree_index, l, r);
int mid = (l + r) / 2;
int64_t a = query(2 * tree_index, l, mid, l_target, r_target);
int64_t b = query(2 * tree_index + 1, mid + 1, r, l_target, r_target);
ST[tree_index] = ST[tree_index] = join(ST[2 * tree_index], ST[2 * tree_index + 1]);
// cout << "Range " << l << ' ' << r << ": " << (a + b) << '\n';
return a + b;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N >> Q >> K;
for (int i = 1; i <= N; i++) {
cin >> C[i];
}
build(1, 1, 1<<17);
while (Q--) {
int S, T, U;
cin >> S >> T >> U;
// cout << S << ' ' << T << ' ' << U << '\n';
if (S == 1) {
edit(1, 1, 1<<17, T, U);
}
else if (S == 2) {
spray(1, 1, 1<<17, T, U);
}
else if (S == 3) {
// cout << '#' << 3 << '\n';
cout << query(1, 1, 1<<17, T, U) << '\n';
}
// cout << "Operation " << S << ": ";
// for (int i = 1; i <= N; i++) {
// cout << query(1, 1, 1<<17, i, i) << ' ';
// }
// cout << '\n';
}
return 0;
}
