#include <bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAX_N = 100000;
const ll INFLL = 10000;
const int MAX_K = 30;
int N, Q;
ll K;
ll C[MAX_N+1];
struct SEG{
struct NODE{
int l, r;
ll d[30];
int lazy;
};
NODE seg[MAX_N*2+1];
int SZ, cnt=0;
void add(){
seg[cnt].l = seg[cnt].r = -1;
seg[cnt].lazy = 0;
cnt++;
}
void Init(int x){
SZ =x ;
add();
init(0, 1, SZ);
}
void init(int idx, int s, int e){
if(s==e){
seg[idx].d[0] = C[s];
for(int i=1; i<MAX_K; i++){
seg[idx].d[i] = seg[idx].d[i-1]/K;
}
return;
}
seg[idx].l = cnt; add();
seg[idx].r = cnt; add();
init(seg[idx].l, s, (s+e)/2);
init(seg[idx].r, (s+e)/2+1, e);
for(int i=0; i<MAX_K; i++){
seg[idx].d[i] = seg[seg[idx].l].d[i]+seg[seg[idx].r].d[i];
}
}
void shift(int idx, int k){
for(int i=0; i<MAX_K; i++){
if(i+k<MAX_K){
seg[idx].d[i] = seg[idx].d[i+k];
}else{
seg[idx].d[i] = 0;
}
}
}
void calc(int idx){
if(seg[idx].l!=-1 && seg[idx].lazy!=0){
if(K==1){
seg[idx].lazy = 0;
return;
}
shift(seg[idx].l, seg[idx].lazy);
shift(seg[idx].r, seg[idx].lazy);
seg[seg[idx].l].lazy+=seg[idx].lazy;
seg[seg[idx].r].lazy+=seg[idx].lazy;
seg[idx].lazy = 0;
}
}
void Update(int x, ll y){
update(0, 1, SZ, x, y);
}
void update(int idx, int s, int e, int x, ll y){
calc(idx);
if(s==e){
seg[idx].d[0] = y;
for(int i=1; i<MAX_K; i++){
seg[idx].d[i] = seg[idx].d[i-1]/K;
}
return;
}
if(x<=(s+e)/2){
update(seg[idx].l, s, (s+e)/2, x, y);
}else{
update(seg[idx].r, (s+e)/2+1, e, x, y);
}
for(int i=0; i<MAX_K; i++){
seg[idx].d[i] = seg[seg[idx].l].d[i]+seg[seg[idx].r].d[i];
}
}
void Lazy(int x, int y){
lazy(0, 1, SZ, x, y);
}
void lazy(int idx, int s, int e, int x, int y){
calc(idx);
if(x<=s && e<=y){
for(int i=0; i<MAX_K-1; i++){
seg[idx].d[i] = seg[idx].d[i+1];
}
seg[idx].d[MAX_K-1] = seg[idx].d[MAX_K-2]/K;
seg[idx].lazy++;
return;
}if(x>e || y<s) return;
lazy(seg[idx].l, s, (s+e)/2, x, y);
lazy(seg[idx].r, (s+e)/2+1, e, x, y);
for(int i=0; i<MAX_K; i++){
seg[idx].d[i] = seg[seg[idx].l].d[i]+seg[seg[idx].r].d[i];
}
}
ll Sum(int x, int y){
return sum(0, 1, SZ, x, y);
}
ll sum(int idx, int s, int e, int x, int y){
calc(idx);
if(x<=s && e<=y) return seg[idx].d[0];
if(x>e || y<s) return 0;
return sum(seg[idx].l, s, (s+e)/2, x, y) + sum(seg[idx].r, (s+e)/2+1, e, x, y);
}
}Seg;
int main(){
scanf("%d%d%lld", &N, &Q, &K);
for(int i =1; i<=N; i++){
scanf("%lld", &C[i]);
}
Seg.Init(N);
for(int i=1; i<=Q; i++){
int t, a, b; scanf("%d%d%d", &t, &a, &b);
if(t==1){
Seg.Update(a, b);
C[a] = b;
}else if(t==2){
Seg.Lazy(a, b);
}else{
printf("%lld\n", Seg.Sum(a, b));
}
}
return 0;
}
