#include <bits/stdc++.h>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define ll long long
#define ff first
#define ss second
#define N 100005
#define MOD 1000000007
#define INF 0x3f3f3f3f
ll bit[N];
ll query(int x){
ll w = 0;
while(x){
w += bit[x];
x -= x & -x;
}
return w;
}
void update(int x, ll w){
while(x < N){
bit[x] += w;
x += x & -x;
}
}
set<int> in;
ll a[N];
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n, q, k;
cin>>n>>q>>k;
for(int i = 1; i <= n; ++i){
cin>>a[i];
update(i, a[i]);
if(a[i])
in.insert(i);
}
while(q--){
int t, l, r;
cin>>t>>l>>r;
if(t == 3)
cout<<query(r) - query(l - 1)<<'\n';
else if(t == 1){
update(l, r - a[l]);
if(a[l] && !r)
in.erase(l);
else if(!a[l] && r)
in.insert(l);
a[l] = r;
} else {
if(k == 1) continue;
auto it = in.lower_bound(l);
while(it != in.end() && *it <= r){
auto f = it++;
update(*f, a[*f] / k - a[*f]);
a[*f] /= k;
if(a[*f] == 0)
in.erase(f);
}
}
}
}
