#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define emb emplace_back
#define fr first
#define sc second
#define all(x) x.begin(),x.end()
#define sp << " " <<
#define N 100000
#define inf 1e9
typedef pair<int,int> ii;
typedef tuple<int,int,int> iii;
typedef array<int,30> arr30;
arr30 operator+(arr30 a,arr30 b){
arr30 ans{};
for(int i=0;i<30;i++)
ans[i]=a[i]+b[i];
return ans;
}
arr30 ff(int x,int k){
if(k==1) return arr30{1};
arr30 ans{};
for(int i=0;x;i++,x/=k)
ans[i]=x%k;
return ans;
}
arr30 st[4*N];
int lz[4*N];
void push(int x){
if(lz[x]==0) return;
if(x<2*N){
lz[x<<1]+=lz[x];
lz[x<<1|1]+=lz[x];
}
for(int i=0;i<30;i++){
if(i+lz[x]<30)
st[x][i]=st[x][i+lz[x]];
else
st[x][i]=0;
}
lz[x]=0;
}
void update(int x,int l,int r,int qx,arr30 val){
push(x);
if(r<qx || qx<l) return;
if(l==r){
st[x]=val;
return;
}
int mid=(l+r)/2;
update(x<<1,l,mid,qx,val);
update(x<<1|1,mid+1,r,qx,val);
st[x]=st[x<<1]+st[x<<1|1];
}
void update(int x,int l,int r,int ql,int qr){
push(x);
if(r<ql || qr<l) return;
if(ql<=l && r<=qr){
lz[x]++;
push(x);
return;
}
int mid=(l+r)/2;
update(x<<1,l,mid,ql,qr);
update(x<<1|1,mid+1,r,ql,qr);
st[x]=st[x<<1]+st[x<<1|1];
}
arr30 query(int x,int l,int r,int ql,int qr){
if(r<ql || qr<l) return arr30{};
push(x);
if(ql<=l && r<=qr)
return st[x];
int mid=(l+r)/2;
return query(x<<1,l,mid,ql,qr)+query(x<<1|1,mid+1,r,ql,qr);
}
void solve(){
int n,q,k;
cin >> n >> q >> k;
for(int i=1;i<=n;i++){
int x;cin >> x;
update(1,1,n,i,ff(x,k));
}
while(q--){
int s,t,u;
cin >> s >> t >> u;
if(s==1)
update(1,1,n,t,ff(u,k));
if(s==2 && k!=1)
update(1,1,n,t,u);
if(s==3){
arr30 a=query(1,1,n,t,u);
int ans=0;
for(int i=0,j=1;i<30 && j<=1e9;i++,j*=k)
ans+=a[i]*j;
cout << ans << "\n";
}
}
}
int32_t main(){
cout << fixed << setprecision(0);
ios_base::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
int test=1;
//~ cin >> test;
while(test--){
solve();
}
}
