#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define int long long
#define ll long long
#define pb push_back
#define fi first
#define se second
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define ld long double
using namespace std;
typedef pair<int,int> pii;
typedef pair<char,char> pcc;
typedef pair<int,pii> ipii;
typedef pair<pii,pii> ipiii;
const int MAXN = 3e5+10;
const int MAXA = 1e6;
const int INF = 1e18+10;
const int MOD = 1e9+7;
const int LOG = 32;
const ld EPS = 1e-12;
int n, q, k, a[MAXN];
struct node {
int val[LOG];
} NOL;
node make(int x){
node ret = NOL;
for(int i=0; i<LOG; i++){
ret.val[i] = x % k;
x /= k;
}
return ret;
}
struct seg {
node st[4*MAXN]; int laz[4*MAXN];
void op(int id, int num){
laz[id] += num;
for(int i=0; i+num<LOG; i++)
st[id].val[i] = st[id].val[i+num];
for(int i=LOG-1; i>=max(0ll,LOG-num); i--)
st[id].val[i] = 0;
}
void bnc(int id, int l, int r){
if(laz[id] == 0) return;
op(lf, laz[id]); op(rg, laz[id]);
laz[id] = 0;
}
node mrg(node a, node b){
node ret = NOL;
for(int i=0; i<LOG; i++)
ret.val[i] = a.val[i]+b.val[i];
return ret;
}
void bd(int id, int l, int r){
if(l==r){ st[id] = make(a[l]); return; }
bd(lf,l,md); bd(rg,md+1,r);
st[id] = mrg(st[lf], st[rg]);
}
node add(int id,int l, int r, int x, int val){
if(x==l && l==r){
laz[id] = 0;
return st[id] = make(val);
}
if(r<x || x<l) return st[id];
bnc(id, l, r);
return st[id] = mrg(add(lf,l,md,x,val), add(rg,md+1,r,x,val));
}
node upd(int id,int l,int r, int x, int y){
if(x<=l && r<=y){
op(id, 1);
return st[id];
}
if(r<x || y<l) return st[id];
bnc(id,l,r);
return st[id] = mrg(upd(lf,l,md,x,y), upd(rg,md+1,r,x,y));
}
node que(int id, int l, int r, int x, int y){
if(x<=l && r<=y) return st[id];
if(r<x || y<l) return NOL;
bnc(id,l,r);
return mrg(que(lf,l,md,x,y), que(rg,md+1,r,x,y));
}
} A;
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
for(int i=0; i<LOG; i++) NOL.val[i] = 0;
cin >> n >> q >> k;
for(int i=1; i<=n; i++) cin >> a[i];
A.bd(1,1,n);
while(q--){
int ty, l, r; cin>>ty>>l>>r;
if(ty==1){
A.add(1,1,n,l,r);
} else if(ty==2){
A.upd(1,1,n,l,r);
} else {
node ret = A.que(1,1,n,l,r);
int ans = 0;
for(int i=LOG-1; i>=0; i--){
ans *= k; ans += ret.val[i];
}
cout << ans << '\n';
}
}
}
