//THIS IS ONLY TRIAL. SOLUTION FROM KAGAMIZ BLOG
#include <bits/stdc++.h>
#define MAX_N (100010)
#define MAX_Q (100010)
#define MAX_S (131072)
using namespace std;
typedef long long Int;
class BIT {
Int A[MAX_N + 1];
public:
BIT(){
memset(A, 0, sizeof(A));
}
void add(int p, Int x){
for (p++; p <= MAX_N; p += p & -p) A[p] += x;
}
Int sum(int p){
Int ret = 0;
for (p++; p; p &= (p - 1)) ret += A[p];
return (ret);
}
};
BIT bit;
int N, Q, K;
int C[MAX_N];
int S[MAX_Q], T[MAX_Q], U[MAX_Q];
pair<int, int> seg[2 * MAX_S - 1];
void update(int k, int x)
{
k += MAX_S - 1;
seg[k] = make_pair(x, k - MAX_S + 1);
while (k){
k = (k - 1) / 2;
seg[k] = max(seg[k * 2 + 1], seg[k * 2 + 2]);
}
}
pair<int, int> getMax(int a, int b, int k = 0, int l = 0, int r = MAX_S)
{
if (b <= l || r <= a) return (make_pair(-1, -1));
if (a <= l && r <= b) return (seg[k]);
pair<int, int> lch = getMax(a, b, k * 2 + 1, l, (l + r) / 2),
rch = getMax(a, b, k * 2 + 2, (l + r) / 2, r);
return (max(lch, rch));
}
void divide(int L, int R)
{
if (L > R) return;
pair<int, int> p = getMax(L, R + 1);
if (p.first == 0) return;
bit.add(p.second, -p.first);
bit.add(p.second, p.first / K);
C[p.second] /= K;
update(p.second, C[p.second]);
divide(L, p.second - 1);
divide(p.second + 1, R);
}
int main()
{
scanf("%d %d %d", &N, &Q, &K);
for (int i = 0; i < N; i++){
scanf("%d", C + i);
}
for (int i = 0; i < Q; i++){
scanf("%d %d %d", S + i, T + i, U + i);
}
for (int i = 0; i < N; i++) bit.add(i, C[i]);
for (int i = 0; i < MAX_S; i++) update(i, i < N ? C[i] : -1);
for (int i = 0; i < Q; i++){
if (S[i] == 1){
update(T[i] - 1, U[i]);
bit.add(T[i] - 1, (Int)U[i] - C[T[i] - 1]);
C[T[i] - 1] = U[i];
}
else if (S[i] == 2){
if (K == 1) continue;
else divide(T[i] - 1, U[i] - 1);
}
else {
printf("%lld\n", bit.sum(U[i] - 1) - bit.sum(T[i] - 2));
}
}
return (0);
}
