#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(false); cin.tie(0)
#define lli long long int
#define nl "\n"
#define rep(i, a, b) for(lli i = (a); i <= (b); ++i)
#define repa(i, a, b) for(lli i = (a); i >= (b); --i)
#define debugsl(x) cout << #x << " = " << x << ", "
#define debug(x) debugsl(x) << nl
#define debugarr(x, a, b) cout << #x << " = ["; rep(i, a, b){ cout << x[i] << ", "; } cout << "]" << nl
#define MAXN 600000
#define MAXPOT 32
#define actplaca 1
#define aerosol 2
#define obtensuma 3
lli n, q, k, maxpot, tmp, tipo, l, r, offset, st[MAXPOT][MAXN], lazy[MAXN];
lli cnt;
void llena(lli nodo, lli x){
if (k == 1){
st[0][nodo] = x;
return;
}
lli pot = 0;
while(x){
st[pot][nodo] = x;
x /= k;
++pot;
}
while(pot <= maxpot) st[pot++][nodo] = 0;
}
void mezcla(lli nodo, lli a, lli b){
rep(i, 0, maxpot) st[i][nodo] = st[i][a] + st[i][b];
}
void divide(lli nodo, lli veces){
rep(i, veces, maxpot) st[i - veces][nodo] = st[i][nodo];
rep(i, max(0ll, maxpot - veces + 1), maxpot) st[i][nodo] = 0;
}
void push(lli nodo, lli s, lli e){
if (lazy[nodo]){
divide(nodo, lazy[nodo]);
if (nodo < offset){
lazy[nodo * 2] += lazy[nodo];
lazy[nodo * 2 + 1] += lazy[nodo];
}
}
lazy[nodo] = 0;
}
void actvalor(lli nodo, lli s, lli e, lli pos, lli val){
push(nodo, s, e);
if (s > pos || e < pos) return;
if (s == pos && e == pos){
llena(nodo, val);
return;
}
lli mitad = (s + e) / 2;
actvalor(nodo * 2, s, mitad, pos, val);
actvalor(nodo * 2 + 1, mitad + 1, e, pos, val);
mezcla(nodo, nodo * 2, nodo * 2 + 1);
}
void actrango(lli nodo, lli s, lli e, lli l, lli r){
push(nodo, s, e);
if (s > r || e < l) return;
if (s >= l && e <= r){
lazy[nodo]++;
push(nodo, s, e);
return;
}
lli mitad = (s + e) / 2;
actrango(nodo * 2, s, mitad, l, r);
actrango(nodo * 2 + 1, mitad + 1, e, l, r);
mezcla(nodo, nodo * 2, nodo * 2 + 1);
}
lli qryrango(lli nodo, lli s, lli e, lli l, lli r){
push(nodo, s, e);
if (s > r || e < l) return 0;
if (s >= l && e <= r) return st[0][nodo];
lli mitad = (s + e) / 2;
return qryrango(nodo * 2, s, mitad, l, r) + qryrango(nodo * 2 + 1, mitad + 1, e, l, r);
}
int main()
{
fastio;
cin >> n >> q >> k;
offset = 1;
while(offset < n) offset <<= 1;
maxpot = 0;
tmp = 1e9 + 1;
while(tmp && k > 1){
++maxpot;
tmp /= k;
}
rep(i, 1, n){
cin >> tmp;
llena(offset + i - 1, tmp);
}
repa(i, offset - 1, 1) mezcla(i, i * 2, i * 2 + 1);
while(q--){
cin >> tipo >> l >> r;
if (tipo == actplaca) actvalor(1, 1, offset, l, r);
else if (tipo == aerosol && k > 1) actrango(1, 1, offset, l, r);
else if (tipo == obtensuma) cout << qryrango(1, 1, offset, l, r) << nl;
}
return 0;
}
