#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template <typename T>
class fenwick {
public :
int n;
vector<T> fen;
explicit fenwick(vector<T> &a) : n(int(a.size())) {
fen.resize(n);
for(int i=0; i<n; i++)modify(i, a[i]);
}
T get(int p){
T v = 0;
while(p >= 0){
v += fen[p];
p = (p & ( p + 1)) - 1;
}
return v;
}
T get(int l, int r){
return (get(r) - get(l - 1));
}
void modify(int p, T v){
assert(0 <= p && p < n);
while(p < n){
fen[p] += v;
p |= (p + 1);
}
}
};
int main(){
ios_base :: sync_with_stdio(false);
cin.tie(nullptr);
int n, q, k;
cin >> n >> q >> k;
vector<ll> a(n);
for(int i=0; i<n; i++)cin >> a[i];
fenwick<ll> d(a);
set<int> b;
for(int i=0; i<n; i++)b.insert(i);
for(int i=0; i<q; i++){
int t, l, r;
cin >> t >> l >> r;
if(t == 1){
d.modify(l - 1, r - a[l - 1]);
a[l - 1] = r;
if(r > 0)b.insert(l - 1);
}
else if(t == 2){
if(k == 1)continue;
vector<int> tem ;
for(auto it = lower_bound(b.begin(), b.end(), l - 1); it != b.end() && (*it) < r; it++){
int x = *it;
if(a[x] == 0){
tem.push_back(x);
continue;
}
d.modify(x, (a[x]/k) - a[x]);
a[x] = a[x]/k;
if(a[x] == 0)tem.push_back(x);
}
for(int &c : tem)b.erase(c);
}else{
cout << d.get(l - 1, r - 1) << '\n';
}
// for(int i=0; i<n; i++)cout << d.get(i, i) << ' ';
// cout << '\n';
}
return 0;
}
