#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Node {
ll sum;
ll mi, ma;
ll n, p;
Node() {
sum = mi = ma = 0;
n = -1, p = 0;
}
Node(ll v) {
sum = mi = ma = v;
n = -1, p = 0;
}
};
struct SegTree {
vector<Node> seg;
int MAX;
SegTree(int N) {
int i;
for(i=1;i<2*N;i*=2) {}
seg.resize(i);
MAX = i;
}
Node f(Node x, Node y) {
Node c;
c.sum = x.sum + y.sum;
c.ma = max(x.ma, y.ma);
c.mi = min(x.mi, y.mi);
c.n = -1;
c.p = 0;
return c;
}
void cons() {
for(int i = MAX/2-1;i>=1;i--) {
seg[i] = f(seg[2*i], seg[2*i+1]);
}
}
void prop(int n, int ns, int ne) {
if(seg[n].n != -1) {
seg[n].ma = seg[n].mi = (seg[n].n + seg[n].p);
seg[n].sum = seg[n].ma * (ne - ns);
if(n<MAX/2) {
seg[2*n].n = seg[n].n;
seg[2*n].p = seg[n].p;
seg[2*n+1].n = seg[n].n;
seg[2*n+1].p = seg[n].p;
}
seg[n].n = -1;
seg[n].p = 0;
}
else {
seg[n].ma += seg[n].p;
seg[n].mi += seg[n].p;
seg[n].sum += seg[n].p * (ne - ns);
if(n<MAX/2) {
seg[2*n].p += seg[n].p;
seg[2*n+1].p += seg[n].p;
}
seg[n].p = 0;
}
}
void add1(int s, int e, ll d, int n, int ns, int ne) {
prop(n,ns,ne);
if(e<=ns||ne<=s) return;
if(s<=ns&&ne<=e) {
seg[n].p += d;
prop(n,ns,ne);
return;
}
int mid = ns + ne >> 1;
add1(s, e, d, 2*n, ns, mid);
add1(s, e, d, 2*n+1, mid, ne);
if(n<MAX/2) seg[n] = f(seg[2*n], seg[2*n+1]);
}
void add2(int s, int e, ll d, int n, int ns, int ne) {
prop(n,ns,ne);
if(e<=ns||ne<=s) return;
if(s<=ns&&ne<=e) {
if(seg[n].ma / d == seg[n].mi / d) {
seg[n].n = seg[n].ma / d;
prop(n,ns,ne);
return;
}// dk-1, dk -> k-1, k
else if(seg[n].mi + 1 == seg[n].ma) {
seg[n].p -= (d-1) * (seg[n].ma / d);
prop(n,ns,ne);
return;
}
}
int mid = ns + ne >> 1;
add2(s, e, d, 2*n, ns, mid);
add2(s, e, d, 2*n+1, mid, ne);
if(n<MAX/2) seg[n] = f(seg[2*n], seg[2*n+1]);
}
ll sum(int s, int e, int n, int ns, int ne) {
prop(n,ns,ne);
if(e<=ns||ne<=s) return 0;
if(s<=ns&&ne<=e) return seg[n].sum;
int mid = ns + ne >> 1;
return sum(s, e, 2*n, ns, mid) + sum(s, e, 2*n+1, mid, ne);
}
};
signed main() {
cin.sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int N, Q, K;
cin >> N >> Q >> K;
SegTree tree(N+5);
int MAX = tree.MAX;
int i, j;
for(i=0;i<N;i++) {
ll a;
cin >> a;
tree.seg[i+MAX/2] = Node(a);
}
tree.cons();
while(Q--) {
ll a, b, c;
cin >> a >> b >>c;
b--;
if(a==1) {
ll val = tree.sum(b, b+1, 1, 0, MAX/2);
tree.add1(b, b+1, c - val, 1, 0, MAX/2);
}
if(a==2) {
if(K != 1) tree.add2(b, c, K, 1, 0, MAX/2);
}
if(a==3) {
cout << tree.sum(b, c, 1, 0, MAX/2) << '\n';
}
}
}
