#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxn = 100010;
set<int> nonz; //nonzero
int N, Q, K;
int nums[maxn];
ll seg[maxn*4];
ll query(int qs, int qe, int ss = 1, int se = N, int si = 0) {
if (qs > qe || ss > se || qs > se || qe < ss) return 0LL;
if (qs <= ss && se <= qe) return seg[si];
int mid = (ss+se)/2;
return query(qs, qe, ss, mid, si*2+1) +
query(qs, qe, mid+1, se, si*2+2);
}
void update(int spot, ll val, int ss = 1, int se = N, int si = 0) {
if (ss == se) {
seg[si] = val;
return;
}
int mid = (ss+se)/2;
if (spot <= mid) update(spot, val, ss, mid, si*2+1);
else update(spot, val, mid+1, se, si*2+2);
seg[si] = seg[si*2+1] + seg[si*2+2];
}
void buildtree(int ss = 1, int se = N, int si = 0) {
if (ss == se) {
seg[si] = nums[ss];
return;
}
int mid = (ss+se)/2;
buildtree(ss, mid, si*2+1);
buildtree(mid+1, se, si*2+2);
seg[si] = seg[si*2+1] + seg[si*2+2];
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> N >> Q >> K;
for (int i = 1; i <= N; i++) {
cin >> nums[i];
if (nums[i]) nonz.insert(i);
}
buildtree();
int tp, a, b;
while (Q--) {
cin >> tp >> a >> b;
if (tp == 1) {
update(a, b);
nums[a] = b;
if (nums[a]) {
nonz.insert(a);
}
}
else if (tp == 2) {
//this is the big one
if (K == 1) continue;
auto it = nonz.lower_bound(a);
while (it != nonz.end() && *it <= b) {
int cur = *it;
nums[cur] = nums[cur]/K;
// cout << cur << " changed to " << nums[cur] << endl;
update(cur, nums[cur]);
if (nums[cur] == 0) {
it = nonz.erase(it);
}
else {
++it;
}
}
}
else {
cout << query(a, b) << '\n';
}
}
cout.flush();
}
