#include <bits/stdc++.h>
#ifdef DEBUG
#include "../templates/debug.h"
#else
#define deb(x...)
#endif
using namespace std;
#define int long long
const int N = 1e5 + 10;
int n,q,k;
int a[N];
struct node{
int mx, sum;
bool checked = false;
} t[4*N];
node nulln = {0,0,false};
node merge(node a, node b){
node ans;
ans.mx = max(a.mx,b.mx);
ans.sum = a.sum + b.sum;
ans.checked = false;
return ans;
}
void push(int v,int tl,int tr){
// deb(v,tl,tr);
if(!t[v].checked)return;
t[v].checked = false;
if(tl != tr){
t[v*2] = t[v*2 + 1] = {0,0,true};
}
}
void propagate(int v,int l,int r){
if(t[v].mx < k){
if(t[v].mx == t[v].sum && t[v].sum == 0){
return;
}
else{
t[v] = {0,0,true};
}
}
else if(l == r){
t[v].mx /= k;
t[v].sum /= k;
}
else{
push(v,l,r);
int tm = (l + r)/2;
propagate(v*2,l,tm);
propagate(v*2 + 1,tm + 1,r);
t[v] = merge(t[v*2],t[v*2 + 1]);
}
}
void build(int v,int tl,int tr){
if(tl == tr)
t[v] = {a[tl],a[tl]};
else{
// push(v,tl,tr);
int tm = (tl + tr)/2;
build(v*2,tl,tm);
build(v*2 + 1,tm + 1,tr);
t[v] = merge(t[v*2],t[v*2 + 1]);
}
}
int query(int l,int r,int v, int tl,int tr){
// deb(l,r,v,tl,tr);
if(l > r)
return 0;
else if(l == tl && r == tr){
return t[v].sum;
}
else{
// assert(tl != tr);
int tm = (tl + tr)/2;
push(v,tl,tr);
return query(l,min(r,tm),v*2,tl,tm) + query(max(l,tm + 1),r,v*2 + 1,tm + 1,tr);
}
}
void update1(int idx,int val, int v,int tl,int tr){
if(tl == tr)
t[v] = {val,val};
else{
push(v,tl,tr);
int tm = (tl + tr)/2;
if(idx <= tm)
update1(idx,val,v*2,tl,tm);
else
update1(idx,val,v*2 + 1,tm + 1,tr);
t[v] = merge(t[v*2],t[v*2 + 1]);
}
}
void update2(int l,int r,int v,int tl,int tr){
if(l > r)
return;
else if(l == tl && r == tr){
propagate(v,tl,tr);
}
else{
if(t[v].checked){
push(v,tl,tr);
return;
}
int tm = (tl + tr)/2;
update2(l,min(r,tm),v*2,tl,tm);
update2(max(l,tm + 1),r,v*2 + 1,tm + 1,tr);
t[v] = merge(t[v*2], t[v*2 + 1]);
}
}
signed main() {
iostream::sync_with_stdio(false);
cin.tie(nullptr);cout.tie(nullptr);
cin >> n >> q >> k;
for(int i = 0;i<n;i++)cin >> a[i];
build(1,0,n-1);
while(q--){
// break;
int t;cin >> t;
if(t == 1){
int a,b;cin >> a >> b;
a--;
update1(a,b,1,0,n-1);
}
else if(t == 2){
int l,r;cin >> l >> r;
l--;r--;
update2(l, r, 1,0,n-1);
}
else{
int l,r;cin >> l >> r;
l--;r--;
cout << query(l,r,1,0,n-1) << "\n";
// break;
}
// for(int i = 0;i<n;i++)
// cout << query(i,i,1,0,n-1) << " ";
// cout << "\n";
}
}
