#include <bits/stdc++.h>
// #include <ext/random>
// #include <ext/pb_ds/assoc_container.hpp>
// #define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define pb push_back
#define ppb pop_back
#define fr first
#define sc second
#define all(v) v.begin(), v.end()
#define vektor vector
using namespace std;
// using namespace __gnu_pbds;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
constexpr ull Mod = 1e6 + 3;
constexpr ull sqr = 547;
constexpr ld eps = 1e-9;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll random(ll l, ll r) {if(l <= r) return uniform_int_distribution <ll> (l, r)(rng); return -1;}
ll st[400005][35], lazy[400005];
int n, Q, k;
void push(int idx, int l, int r){
if(lazy[idx] != 0){
for(ll j = lazy[idx]; j <= 34; j ++){
if(k != 1) st[idx][j - lazy[idx]] = 0;
swap(st[idx][j], st[idx][j - lazy[idx]]);
}
if(l != r){
lazy[idx << 1] += lazy[idx];
lazy[idx << 1 | 1] += lazy[idx];
}
lazy[idx] = 0;
}
}
void update(int idx, int l, int r, int u, int v){
push(idx, l, r);
if(v < l || r < u) return;
if(u <= l && r <= v){
lazy[idx] ++;
push(idx, l, r);
return;
}
int mid = (l + r) >> 1;
update(idx << 1, l, mid, u, v);
update(idx << 1 | 1, mid + 1, r, u, v);
for(int j = 0; j <= 34; j ++) st[idx][j] = st[idx << 1][j] + st[idx << 1 | 1][j];
}
void update2(int idx, int l, int r, int i, int val, int prevval){
push(idx, l, r);
int val1 = prevval, j = 0;
while(val1 && j <= 34){
st[idx][j] -= val1;
val1 /= k;
j ++;
}
j = 0;
val1 = val;
while(val1 && j <= 34){
st[idx][j] += val1;
val1 /= k;
j ++;
}
if(l == r) return;
int mid = (l + r) >> 1;
if(i <= mid) update2(idx << 1, l, mid, i, val, prevval);
else update2(idx << 1 | 1, mid + 1, r, i, val, prevval);
for(int j = 0; j <= 34; j ++) st[idx][j] = st[idx << 1][j] + st[idx << 1 | 1][j];
}
ll query(int idx, int l, int r, int u, int v){
push(idx, l, r);
if(v < l || r < u) return 0;
if(u <= l && r <= v) return st[idx][0];
int mid = (l + r) >> 1;
return query(idx << 1, l, mid, u, v) + query(idx << 1 | 1, mid + 1, r, u, v);
}
void solve(){
memset(st, 0, sizeof(st));
memset(lazy, 0, sizeof(lazy));
cin >> n >> Q >> k;
for(int i = 1; i <= n; i ++) {
int x;
cin >> x;
update2(1, 1, n, i, x, 0);
}
while(Q --){
int type, l, r;
cin >> type >> l >> r;
if(type == 1){
int prevval = query(1, 1, n, l, l);
update2(1, 1, n, l, r, prevval);
}
if(type == 2){
update(1, 1, n, l, r);
}
if(type == 3) cout << query(1, 1, n, l, r) << "\n";
}
}
main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
if(fopen("nameholder.inp", "r")){
freopen("nameholder.inp", "r", stdin);
freopen("nameholder.out", "w", stdout);
}
int t = 1;
while(t --){
solve();
}
}
