#include "bits/stdc++.h"
using namespace std;
#define int long long
#define fi first
#define se second
#define pii pair<int,int>
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define pb push_back
#define ll long long
const int N = 1e5+5;
const int LG = 20;
int n,q,k, a[N];
namespace sub{
struct BIT{
ll bit[N];
void upd(int i, int x){
for(;i<=n;i+=i&-i) bit[i]+=x;
}
ll get(int i){
ll ans =0;
for(;i;i-=i&-i) ans+= bit[i];
return ans;
}
}bit;
void solve(){
for(int i=1;i<=n;i++) bit.upd(i,a[i]);
while(q--){
int t,u,v; cin>>t>>u>>v;
if(t==1){
bit.upd(u,v-bit.get(u));
}
else if(t==2){
continue;
}
else cout<<bit.get(v)- bit.get(u-1)<<"\n";
}
}
}
struct Node{
int dt[LG], lz;
void combine(Node &a, Node &b){
for(int i=0;i<LG;i++) dt[i] = a.dt[i]+ b.dt[i];
}
ll toNum(){
ll ans =0;
for(int i=LG-1;i>=0;i--){
ans = ans*k + dt[i];
}
return ans;
}
}tr[4*N];
void app_lz(Node &a, int lz){
a.lz+= lz;
if(lz>=LG) {
memset(a.dt,0,sizeof(a.dt));
return;
}
memmove(a.dt, a.dt+lz, (LG-lz)*sizeof(lz));
}
void down(int id){
if(!tr[id].lz) return;
int t= tr[id].lz;
app_lz(tr[2*id], t);
app_lz(tr[2*id+1],t);
tr[id].lz =0;
}
void encode(int dt[], int x){
for(int i=0;i<LG;i++){
dt[i] = x%k;
x/=k;
}
}
void build(int id, int l, int r){
if(l==r){
encode(tr[id].dt, a[l]);
return;
}
int mid=(l+r)>>1;
build(2*id,l,mid);
build(2*id+1,mid+1,r);
tr[id].combine(tr[2*id], tr[2*id+1]);
}
void upd1(int id, int l, int r, int p, int v){
if(l>p||r<p) return;
if(l==r){
encode(tr[id].dt, v);
return;
}
int mid=(l+r)>>1;
down(id);
upd1(2*id,l,mid,p,v);
upd1(2*id+1,mid+1,r,p,v);
tr[id].combine(tr[2*id], tr[2*id+1]);
}
void upd2(int id, int l, int r, int t_l ,int t_r){
if(l>t_r||r<t_l) return;
if(t_l<=l&&r<=t_r){
app_lz(tr[id], 1);
return;
}
int mid=(l+r)>>1;
down(id);
upd2(2*id,l,mid,t_l,t_r);
upd2(2*id+1,mid+1,r,t_l,t_r);
tr[id].combine(tr[2*id], tr[2*id+1]);
}
ll get(int id, int l, int r, int t_l ,int t_r){
if(l>t_r||r<t_l) return 0;
if(t_l<=l&&r<=t_r) return tr[id].toNum();
int mid=(l+r)>>1;
down(id);
return get(2*id,l,mid,t_l,t_r)+get(2*id+1,mid+1,r,t_l,t_r);
}
signed main(){
ios_base::sync_with_stdio(NULL);
cin.tie(NULL);
if(fopen("TASK.INP", "r")){
freopen("TASK.INP", "r", stdin);
freopen("TASK.OUT", "w", stdout);
}
cin>>n>>q>>k;
for(int i=1;i<=n;i++) cin>>a[i];
if(k==1) return sub::solve(),0;
build(1,1,n);
while(q--){
int t,u,v; cin>>t>>u>>v;
if(t==1){
upd1(1,1,n,u,v);
}
else if(t==2){
upd2(1,1,n,u,v);
}
else cout<<get(1,1,n,u,v)<<"\n";
}
}
