#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<ll, ll>
#define fi first
#define sec second
#define ld long double
const ll N = 1e5;
const ll INF = 4e18;
const ll MOD = 998244353;
struct BIT{
ll n;
vector<ll> bit;
BIT (ll _n){
n = _n;
bit.resize(n + 5);
}
void upd(ll idx, ll val) { for(int i = idx; i <= n; i += i & -i) bit[i] += val; }
ll get(ll idx){ ll ans = 0; for(int i = idx; i >= 1; i -= i & -i) ans += bit[i]; return ans; }
ll query(ll l, ll r){ return get(r) - get(l - 1); }
};
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int tc = 1;
// cin >> tc;
for(;tc--;){
ll n, q, k; cin >> n >> q >> k;
vector<ll> a(n + 5);
set<ll> st;
BIT bit(n);
for(int i = 1; i <= n; i++){
cin >> a[i];
bit.upd(i, a[i]);
if(a[i]) st.insert(i);
}
for(int i = 1; i <= q; i++){
ll s, t, u; cin >> s >> t >> u;
if(s == 1){
if(u == 0){
if(st.find(t) != st.end()) st.erase(t);
}
else st.insert(t);
bit.upd(t, u - a[t]);
a[t] = u;
}
else if(s == 2){
if(k == 1) continue;
vector<ll> del;
for(auto x = st.lower_bound(t); x != st.end() && (*x) <= u; x++){
bit.upd((*x), a[*x] / k - a[*x]);
a[*x] /= k;
if(!a[*x]) del.push_back(*x);
}
for(auto x : del) st.erase(x);
}
else{
cout << bit.query(t, u) << "\n";
}
}
}
}
/*
*/
