#include <bits/stdc++.h>
using namespace std;
const int N = 100001;
int n;
int k;
long long t[N*4];
void upd_plus(int i, int value, int l = 1, int r = n, int pos = 1){
int mid = (l+r)/2;
if(l == r){
t[pos] = value;
return;
}
if (mid >= i){
upd_plus(i, value, l, mid, pos*2);
}
else if (mid < i){
upd_plus(i, value, mid+1, r, pos*2+1);
}
t[pos] = t[pos*2]+t[pos*2+1];
}
long long find_sum(int lb,int rb, int l = 1, int r = n, int pos = 1){
if(lb>r || rb<l){
return 0;
}
if(l>=lb && r<=rb){
return t[pos];
}
int mid = (l+r)/2;
return find_sum(lb, rb, l, mid, pos*2) + find_sum(lb,rb, mid+1, r, pos*2+1);
}
int main()
{
ios_base::sync_with_stdio(false); cin.tie(nullptr);
int q; cin >> n >> q >> k;
int c[n+1];
set<int> notZero;
for(int i = 1; i <= n; i++){
cin >> c[i];
upd_plus(i, c[i]);
if(c[i]!=0)
notZero.insert(i);
}
if(k==1){
while(q--){
int s; cin >> s;
if(s==1){
int a, b; cin >> a >> b;
upd_plus(a,b);
}
else if (s==2){
int l, r;
cin >> l >> r;
}
else if (s==3){
int l, r; cin >> l >> r;
cout << find_sum(l,r) << '\n';
}
}
return 0;
}
while(q--){
int s; cin >> s;
if(s==1){
int a, b; cin >> a >> b;
upd_plus(a,b);
c[a] = b;
if(b==0)
notZero.erase(a);
else
notZero.insert(a);
}
else if (s==2){
int l, r; cin >> l >> r;
auto it = notZero.lower_bound(l);
while(it != notZero.end() && *it <= r){
c[*it]/=k;
upd_plus(*it, c[*it]);
if(c[*it]==0){
notZero.erase(it);
l=*it;
}
else
l = *it+1;
it = notZero.lower_bound(l);
}
}
else{
int l, r; cin >> l >> r;
cout << find_sum(l,r) << '\n';
}
}
return 0;
}
