#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll // delete if causing problems
#define pb push_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second
#define mod(a) (a+MOD)%MOD
#define all(a) a.begin(), a.end()
#define sz(a) (int)a.size()
const int mxN = (int)3e5+10; // change when needed!
int n, k, q, a[mxN];
struct Data{
int mx, mx2, mxcnt, sum;
} segTree[2*mxN];
int lazy[2*mxN];
void prop(int p, int l, int r){
if(l==r or lazy[p]<0) return;
int m = (l+r)/2;
int lp = p+1, rp = p+2*(m-l+1);
lazy[lp]=lazy[rp]=lazy[p];
segTree[lp].mx=segTree[rp].mx=segTree[p].mx;
segTree[lp].mx2=segTree[rp].mx2=segTree[p].mx2;
segTree[lp].mxcnt=(m-l+1), segTree[p].mxcnt=(r-m);
segTree[lp].sum=(m-l+1)*segTree[lp].mx;
segTree[rp].sum=(r-m)*segTree[rp].mx;
lazy[p]=-1;
}
Data combine(Data &a, Data &b){
Data c; c.sum=a.sum+b.sum;
if(a.mx>b.mx){
c.mx=a.mx; c.mxcnt=a.mxcnt;
if(a.mx2>b.mx) c.mx2=a.mx2;
else c.mx2=b.mx;
}
else if(a.mx<b.mx){
c.mx=b.mx; c.mxcnt=b.mxcnt;
if(b.mx2>a.mx) c.mx2=b.mx2;
else c.mx2=a.mx;
}
else{
c.mx=a.mx, c.mxcnt=a.mxcnt+b.mxcnt;
if(a.mx2>b.mx2)c.mx2=a.mx2;
else c.mx2=b.mx2;
}
return c;
}
void upd(int i, int j, int v, int t, int p=0, int l=1, int r=n){
if(i>r or j<l or i>j) return; prop(p,l,r);
int m = (l+r)/2; int lp = p+1, rp = p+2*(m-l+1);
if(i<=l and r<=j){
if(!t){
segTree[p].sum=segTree[p].mx=v;
segTree[p].mxcnt=1, segTree[p].mx2=-1;
return;
}
if(segTree[p].mx<v){
segTree[p].sum=0; lazy[p]=0;
segTree[p].mx=0;
segTree[p].mxcnt=(r-l+1);
segTree[p].mx2=-1;
return;
}
if(segTree[p].mx2<v){
int nv = segTree[p].mx/v;
segTree[p].sum=nv*segTree[p].mxcnt;
lazy[p]=nv;
//assign all elements in l to r = 0 (excluding those =mx)
segTree[p].mx=nv;
segTree[p].mxcnt=(r-l+1);
segTree[p].mx2=-1;
return;
}
}
upd(i,j,v,t,lp,l,m),upd(i,j,v,t,rp,m+1,r);
segTree[p] = combine(segTree[lp],segTree[rp]);
}
int query(int i, int j, int p=0, int l=1, int r=n){
if(i>r or j<l or i>j) return 0; prop(p,l,r);
if(i<=l and r<=j) return segTree[p].sum;
int m = (l+r)/2; int lp=p+1, rp = p+2*(m-l+1);
return query(i,j,lp,l,m)+query(i,j,rp,m+1,r);
}
void solve()
{
cin >> n >> q >> k; fill(lazy,lazy+2*mxN,-1);
for(int i = 1; i <= n; i++) cin >> a[i], upd(i,i,a[i],0);
while(q--){
int t, x, y; cin >> t >> x >> y;
if(t==1) upd(x, x, y, 0);
else if(t==2){
if(k>1) upd(x, y, k, 1);
}
else cout << query(x,y) << "\n";
}
}
int32_t main()
{
ios_base::sync_with_stdio(false); cin.tie(0);
int t = 1; //cin >> t;
while(t--) solve();
}
