// IN THE NAME OF ALLAH
#include<bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL)
#define wall cerr << "------------------------------------" << endl
#define pb push_back
#define pob pop_back
#define F first
#define S second
#define all(x) x.begin() , x.end()
#define scan scanf
#define print printf
#define outs(x) print("%lld " , x)
#define out(x) print("%lld\n" , x)
#define in(x) scan("%lld" , &x)
#define gcd __gcd
#define endl '\n'
#define int ll
#pragma GCC optimize("Ofast")
typedef long long ll;
typedef pair<int , int> pii;
typedef pair<ll , ll> pll;
typedef pair<pii , int> piii;
typedef pair<pll , ll> plll;
const int N = 1e5+10;
const int K = 31 + 10;
const ll mod = 1e9+7;
const ll INF = 1e18+10;
const int P = 31;
int seg[4*N][K];
int la[4*N];
int n , q , k;
int a[N];
void build(int v , int tl , int tr) {
if(tl == tr) {
int x = a[tl];
seg[v][0] = x;
int o = 1;
while(x && o < K) {
x /= k;
seg[v][o++] = x;
}
return;
}
int tm = (tl + tr)/2;
build(2*v , tl , tm);
build(2*v+1 , tm+1 , tr);
for(int i = 0 ; i < K ; i++)
seg[v][i] = seg[2*v][i] + seg[2*v+1][i];
}
void shift(int v , int tl , int tr) {
for(int i = 0 ; i <= K - la[v] - 1 ; i++)
seg[v][i] = seg[v][i+la[v]];
for(int i = K-1 ; i > K-la[v]-1 && i >= 0 ; i--)
seg[v][i] = 0;
if(tl != tr) {
la[2*v] += la[v];
la[2*v+1] += la[v];
}
la[v] = 0;
}
void update(int v , int tl , int tr , int pos , int x) {
shift(v , tl , tr);
if(tl > pos || pos > tr)
return;
if(tl == tr) {
int y = x;
seg[v][0] = y;
int o = 1;
while(y && o < K) {
y /= k;
seg[v][o++] = y;
}
return;
}
int tm = (tl + tr)/2;
update(2*v , tl , tm , pos , x);
update(2*v+1 , tm+1 , tr , pos , x);
for(int i = 0 ; i < K ; i++)
seg[v][i] = seg[2*v][i] + seg[2*v+1][i];
}
void upd(int v , int tl , int tr , int l , int r) {
shift(v , tl , tr);
if(l > r)
return;
if(tl == l && tr == r) {
la[v] = 1;
shift(v , tl , tr);
return;
}
int tm = (tl + tr)/2;
upd(2*v , tl , tm , l , min(tm , r));
upd(2*v+1 , tm+1 , tr , max(l , tm+1) , r);
for(int i = 0 ; i < K ; i++)
seg[v][i] = seg[2*v][i] + seg[2*v+1][i];
}
int ask(int v , int tl , int tr , int l , int r) {
shift(v , tl , tr);
if(l > r)
return 0;
if(tl == l && tr == r)
return seg[v][0];
int tm = (tl + tr)/2;
return ask(2*v , tl , tm , l , min(tm , r)) + ask(2*v+1 , tm+1 , tr , max(l , tm+1) , r);
}
signed main()
{
fast;
cin >> n >> q >> k;
for(int i = 1 ; i <= n ; i++)
cin >> a[i];
build(1 , 1 , n);
if(k == 1) {
while(q--) {
int t , l , r;
cin >> t >> l >> r;
if(t == 1)
update(1 , 1 , n , l , r);
else if(t == 3)
cout << ask(1 , 1 , n , l , r) << "\n";
}
}
else {
while(q--) {
int t , l , r;
cin >> t >> l >> r;
if(t == 1)
update(1 , 1 , n , l , r);
else if(t == 2)
upd(1 , 1 , n , l , r);
else
cout << ask(1 , 1 , n , l , r) << "\n";
}
}
}
// IT'S EASY TO SEE
