#include<bits/stdc++.h>
using namespace std;
#define MASK(i) (1LL << (i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define fi first
#define base 31
#define sz(x) (int)(x).size()
#define se second
#define ll long long
#define pb push_back
#define pii pair<int, int>
#define all(x) (x).begin(), (x).end()
#define name "name"
const int oo = 1e9 + 7;
const ll loo = (ll)1e18 + 7;
const int MOD = 1e9 + 7;
const int N = 2e5 + 3;
template <typename T1, typename T2> bool minimize(T1 &a, T2 b){if (a > b) {a = b; return true;} return false;}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b){if (a < b) {a = b; return true;} return false;}
int n , q , k;
int a[N];
struct SEGTREE{
int lazy[N << 2];
vector<ll> st[N << 2];
void build(int id , int l , int r){
st[id].assign(33 , 0);
if(l == r){
st[id][30] = a[l];
for(int i = 29 ; i >= 0 ; i--) st[id][i] = st[id][i + 1] / k;
return;
}
int mid = l + r >> 1;
build(id << 1 , l , mid);
build(id << 1 | 1 , mid + 1 , r);
for(int i = 0 ; i <= 30 ; i++) st[id][i] = st[id << 1][i] + st[id << 1 | 1][i];
}
void down(int id , int l , int r){
int val = lazy[id];
if(val == 0) return;
lazy[id] = 0;
minimize(val, 30);
for(int i = 30 ; i >= val ; i--){
st[id << 1][i] = st[id << 1][i - val];
st[id << 1 | 1][i] = st[id << 1 | 1][i - val];
}
for(int i = val - 1 ; i >= 0 ; i--){
st[id << 1][i] = st[id << 1][i + 1] / k;
st[id << 1 | 1][i] = st[id << 1 | 1][i + 1] / k;
}
lazy[id << 1] += val;
lazy[id << 1 | 1] += val;
}
void update1(int id , int l , int r , int t , int v){
if(l > t || r < t) return;
if(l == r){
st[id][30] = v;
for(int i = 29 ; i >= 0 ; i--) st[id][i] = st[id][i + 1] / k;
return;
}
int mid = l + r >> 1;
down(id , l , r);
update1(id << 1 , l , mid , t , v);
update1(id << 1 | 1 , mid + 1 , r , t , v);
for(int i = 0 ; i <= 30 ; i++) st[id][i] = st[id << 1][i] + st[id << 1 | 1][i];
}
void update(int id , int l , int r , int u , int v){
if(l > v || r < u) return;
if(u <= l && r <= v){
for(int i = 30 ; i > 0 ; i--) st[id][i] = st[id][i - 1];
st[id][0] = st[id][1] / k;
lazy[id]++;
return;
}
int mid = l + r >> 1;
down(id , l , r);
update(id << 1 , l , mid , u , v);
update(id << 1 | 1 , mid + 1 , r , u , v);
for(int i = 0 ; i <= 30 ; i++) st[id][i] = st[id << 1][i] + st[id << 1 | 1][i];
}
ll get(int id , int l , int r , int u , int v){
if(l > v || r < u) return 0;
if(u <= l && r <= v) return st[id][30];
int mid = l + r >> 1;
down(id , l , r);
return get(id << 1 , l , mid , u , v) + get(id << 1 | 1 , mid + 1 , r , u , v);
}
}segtree;
void input(){
cin >> n >> q >> k;
for(int i = 1 ; i <= n ; i++) cin >> a[i];
segtree.build(1 , 1 , n);
}
void solve(){
while(q--){
int type;
cin >> type;
if(type == 1){
int i , x;
cin >> i >> x;
segtree.update1(1 , 1 , n , i , x);
}
if(type == 2){
int l , r;
cin >> l >> r;
segtree.update(1 , 1 , n , l , r);
}
if(type == 3){
int l , r;
cin >> l >> r;
cout << segtree.get(1 , 1 , n , l , r) << '\n';
}
}
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);
if (fopen(name".inp", "r")){
freopen(name".inp", "r", stdin);
freopen(name".out", "w", stdout);
}
input();
solve();
}
// author: thefless
