#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// Dùng long long vì tổng có thể vượt quá 2^31
typedef long long ll;
const int MAXN = 100005;
struct Node {
ll sum;
ll max_val;
};
int N, Q;
ll K;
ll arr[MAXN];
Node tree[4 * MAXN];
// Hàm hợp nhất hai nút con
Node merge(Node left, Node right) {
Node res;
res.sum = left.sum + right.sum;
res.max_val = max(left.max_val, right.max_val);
return res;
}
// Xây dựng cây
void build(int node, int start, int end) {
if (start == end) {
tree[node].sum = arr[start];
tree[node].max_val = arr[start];
} else {
int mid = (start + end) / 2;
build(2 * node, start, mid);
build(2 * node + 1, mid + 1, end);
tree[node] = merge(tree[2 * node], tree[2 * node + 1]);
}
}
// Thao tác 1: Cập nhật điểm (Point Update)
void update_point(int node, int start, int end, int idx, ll val) {
if (start == end) {
tree[node].sum = val;
tree[node].max_val = val;
} else {
int mid = (start + end) / 2;
if (start <= idx && idx <= mid) {
update_point(2 * node, start, mid, idx, val);
} else {
update_point(2 * node + 1, mid + 1, end, idx, val);
}
tree[node] = merge(tree[2 * node], tree[2 * node + 1]);
}
}
// Thao tác 2: Cập nhật đoạn (Range Update - Division)
void update_range_div(int node, int start, int end, int l, int r) {
// Nếu đoạn hiện tại nằm ngoài phạm vi cần update hoặc max_val = 0 (chia cũng bằng 0)
if (start > end || start > r || end < l || tree[node].max_val == 0) {
return;
}
// Nếu là nút lá, thực hiện chia
if (start == end) {
tree[node].sum /= K;
tree[node].max_val /= K;
return;
}
// Nếu không phải lá, đi xuống con
int mid = (start + end) / 2;
update_range_div(2 * node, start, mid, l, r);
update_range_div(2 * node + 1, mid + 1, end, l, r);
// Cập nhật lại nút cha sau khi con thay đổi
tree[node] = merge(tree[2 * node], tree[2 * node + 1]);
}
// Thao tác 3: Truy vấn tổng (Range Sum Query)
ll query(int node, int start, int end, int l, int r) {
if (start > end || start > r || end < l) {
return 0;
}
if (l <= start && end <= r) {
return tree[node].sum;
}
int mid = (start + end) / 2;
ll p1 = query(2 * node, start, mid, l, r);
ll p2 = query(2 * node + 1, mid + 1, end, l, r);
return p1 + p2;
}
int main() {
// Tối ưu nhập xuất
ios_base::sync_with_stdio(false);
cin.tie(NULL);
if (!(cin >> N >> Q >> K)) return 0;
for (int i = 1; i <= N; i++) {
cin >> arr[i];
}
build(1, 1, N);
for (int i = 0; i < Q; i++) {
int type;
cin >> type;
if (type == 1) {
int idx;
ll val;
cin >> idx >> val;
update_point(1, 1, N, idx, val);
} else if (type == 2) {
int l, r;
cin >> l >> r;
// Nếu K = 1, phép chia không thay đổi gì, bỏ qua để tiết kiệm thời gian
if (K > 1) {
update_range_div(1, 1, N, l, r);
}
} else if (type == 3) {
int l, r;
cin >> l >> r;
cout << query(1, 1, N, l, r) << "\n";
}
}
return 0;
}
