#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 5;
int n, q, k, a[N];
set<int> s;
struct fenwick{
int t[N];
void upd(int i, int x){
for(; i<N; i += i & -i) t[i] += x;
}
int qry(int i){
int res = 0;
for(; i>0; i -= i & -i) res += t[i];
return res;
}
}fw;
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> q >> k;
for(int i = 1;i<=n;i++){
cin >> a[i];
fw.upd(i, a[i]);
if(a[i] != 0) s.insert(i);
}
while(q--){
int tt, l, r;
cin >> tt >> l >> r;
if(tt == 1){
fw.upd(l, r - a[l]);
a[l] = r;
if(a[l] != 0) s.insert(l);
}else if(tt == 2 && k != 1){
auto itl = s.lower_bound(l), itr = s.upper_bound(r);
vector<int> t;
for(auto it = itl;it != itr;it++){
int nw = a[*it] / k;
fw.upd(*it, nw - a[*it]);
a[*it] = nw;
if(a[*it] == 0) t.push_back(*it);
}
for(auto x : t) s.erase(x);
}else if(tt == 3){
cout << fw.qry(r) - fw.qry(l - 1) << '\n';
}
}
}
