// __builtin_popcount(x)
// __builtin_popcountll(x)
#define here cerr<<"===========================================\n"
#include <bits/stdc++.h>
#define ld double
#define ll long long
#define ull unsigned long long
#define llinf 100000000000000000LL // 10^17
#define iinf 2000000000 // 2*10^9
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) int(a.size())
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
using namespace std;
#define maxn 200005
ll n,q,k;
ll a[maxn];
ll lazy[4*maxn];
vector<ll> t[4*maxn];
vector<ll> mrg(vector<ll> a,vector<ll> b){
vector<ll> c(20);
for(ll i = 0;i<20;i++) c[i] = a[i] + b[i];
return c;
}
vector<ll> f(ll x){
vector<ll> c(20);
ll y = x;
for(ll i = 0;i<20;i++){
c[i] = y;
y/=k;
}
return c;
}
void push(ll v,ll tl,ll tr){
ll x = lazy[v];
while(lazy[v]>0&&t[v][0]>0){
for(ll i = 0;i<19;i++) t[v][i] = t[v][i+1];
t[v][19] = 0;
lazy[v]--;
}
lazy[v] = x;
if(tl<tr){
lazy[2*v]+=lazy[v];
lazy[2*v+1]+=lazy[v];
}
lazy[v] = 0;
}
void init(ll v,ll tl,ll tr){
if(tl==tr){
t[v] = f(a[tl]);
return;
}
ll mid = (tl+tr)/2;
init(2*v,tl,mid);
init(2*v+1,mid+1,tr);
t[v] = mrg(t[2*v],t[2*v+1]);
}
void upd(ll v,ll tl,ll tr,ll l,ll r){
push(v,tl,tr);
if(l>r) return;
if(tl==l&&tr==r){
lazy[v]++;
push(v,tl,tr);
return;
}
ll mid = (tl+tr)/2;
upd(2*v,tl,mid,l,min(mid,r));
upd(2*v+1,mid+1,tr,max(mid+1,l),r);
push(2*v,tl,mid);
push(2*v+1,mid+1,tr);
t[v] = mrg(t[2*v],t[2*v+1]);
}
ll get(ll v,ll tl,ll tr,ll l,ll r){
push(v,tl,tr);
if(l>r) return 0;
if(tl==l&&tr==r) return t[v][0];
ll mid = (tl+tr)/2;
return get(2*v,tl,mid,l,min(mid,r)) + get(2*v+1,mid+1,tr,max(mid+1,l),r);
}
void check(ll v,ll tl,ll tr){
cerr<<"range: "<<tl<< " "<<tr<<endl;
for(ll x : t[v]) cerr<<x<< " ";
cerr<<endl;
if(tl==tr) return;
ll mid = (tl+tr)/2;
check(2*v,tl,mid);
check(2*v+1,mid+1,tr);
}
void upd2(ll v,ll tl,ll tr,ll i,ll x){
push(v,tl,tr);
if(tl==tr){
t[v] = f(x);
return;
}
ll mid = (tl+tr)/2;
if(i<=mid) upd2(2*v,tl,mid,i,x);
else upd2(2*v+1,mid+1,tr,i,x);
push(2*v,tl,mid);
push(2*v+1,mid+1,tr);
t[v] = mrg(t[2*v],t[2*v+1]);
}
int main(){
ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);
cin >> n >> q >> k;
for(ll i = 1;i<=n;i++) cin >> a[i];
init(1,1,n);
while(q--){
ll tip; cin >> tip;
if(tip==1){
ll i,x;
cin >> i >> x;
upd2(1,1,n,i,x);
}else if(tip==2){
ll l,r; cin >> l >> r;
if(k==1) continue;
upd(1,1,n,l,r);
}else{
ll l,r; cin >> l >> r;
cout<<get(1,1,n,l,r)<<endl;
}
}
return 0;
}
