#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr int LIM = 1e5;
constexpr int base = (1 << 17);
ll tri[2 * base];
int tab[LIM + 10];
void upd(int v, int x) {
v += base;
tri[v] = x;
v /= 2;
while(v > 0) {
tri[v] = tri[2 * v] + tri[2 * v + 1];
v /= 2;
}
}
ll que(int l, int r) {
l += base;
r += base;
ll ans = 0;
while(l <= r) {
if(l & 1) {
ans += tri[l];
}
if(!(r & 1)) {
ans += tri[r];
}
l = (l + 1) / 2;
r = (r - 1) / 2;
}
return ans;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, k, t;
cin >> n >> t >> k;
set<int>s;
for(int i = 1; i <= n; i++) {
cin >> tab[i];
if(tab[i]) {
s.insert(i);
}
upd(i, tab[i]);
}
while(t--) {
int tp;
cin >> tp;
if(tp == 1) {
int a, b;
cin >> a >> b;
tab[a] = b;
if(b) {
s.insert(a);
}
upd(a, b);
}
else if(tp == 2 && k > 1) {
int l, r;
cin >> l >> r;
vector<int>us;
auto it = s.lower_bound(l);
while(it != s.end() && *it <= r) {
tab[*it] /= k;
upd(*it, tab[*it]);
if(!tab[*it]) {
us.push_back(*it);
}
it++;
}
for(auto x : us) {
s.erase(x);
}
}
else {
int l, r;
cin >> l >> r;
cout << que(l, r) << '\n';
}
}
}
