#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 1e5 + 10;
const int MAXX = 50;
int N, Q, K;
struct node
{
array<int, MAXX> sum;
int lz;
node(array<int, MAXX> S = { 0 }, int LZ = 0) : sum(S), lz(LZ) {}
node operator+(node outro)
{
node resp;
for (int i = 0; i < MAXX; i++) resp.sum[i] = sum[i] + outro.sum[i];
return resp;
}
};
array<node, 4*MAXN> seg;
array<int, MAXN> v;
void refresh(int pos, int ini, int fim)
{
if (seg[pos].lz == 0) return;
int x = seg[pos].lz; seg[pos].lz = 0;
for (int i = 0; i + x < MAXX; i++) seg[pos].sum[i] = seg[pos].sum[i+x];
for (int i = MAXX - x; i < MAXX; i++) seg[pos].sum[i] = 0;
if (ini == fim) return;
int e = 2*pos; int d = 2*pos + 1;
seg[e].lz += x;
seg[d].lz += x;
}
void updatePlaca(int pos, int ini, int fim, int id, int val)
{
refresh(pos, ini, fim);
if (id < ini || id > fim) return;
if (ini == fim)
{
seg[pos].sum[0] = val;
for (int x = 1; x < MAXX; x++) seg[pos].sum[x] = (seg[pos].sum[x-1]/K);
seg[pos].lz = 0;
return;
}
int m = (ini + fim) >> 1;
int e = 2*pos; int d = 2*pos + 1;
updatePlaca(e, ini, m, id, val);
updatePlaca(d, m+1, fim, id, val);
seg[pos] = seg[e] + seg[d];
}
void updateSpray(int pos, int ini, int fim, int p, int q)
{
refresh(pos, ini, fim);
if (K == 1) return;
if (q < ini || p > fim) return;
if (p <= ini && fim <= q)
{
seg[pos].lz++;
refresh(pos, ini, fim);
return;
}
int m = (ini + fim) >> 1;
int e = 2*pos; int d = 2*pos + 1;
updateSpray(e, ini, m, p, q);
updateSpray(d, m+1, fim, p, q);
seg[pos] = seg[e] + seg[d];
}
int query(int pos, int ini, int fim, int p, int q)
{
refresh(pos, ini, fim);
if (q < ini || p > fim) return 0;
if (p <= ini && fim <= q) return seg[pos].sum[0];
int m = (ini + fim) >> 1;
int e = 2*pos; int d = 2*pos + 1;
return (query(e, ini, m, p, q) + query(d, m+1, fim, p, q));
}
void build(int pos, int ini, int fim)
{
if (ini == fim)
{
seg[pos].sum[0] = v[ini];
for (int x = 1; x < MAXX; x++) seg[pos].sum[x] = (seg[pos].sum[x-1]/K);
seg[pos].lz = 0;
return;
}
int m = (ini + fim) >> 1;
int e = 2*pos; int d = 2*pos + 1;
build(e, ini, m);
build(d, m+1, fim);
seg[pos] = seg[e] + seg[d];
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> N >> Q >> K;
for (int i = 1; i <= N; i++) cin >> v[i];
build(1, 1, N);
bool b = false;
while (Q--)
{
int type;
cin >> type;
//Update Placa
if (type == 1)
{
int id, val;
cin >> id >> val;
updatePlaca(1, 1, N, id, val);
}
//Update Spray
else if (type == 2)
{
int L, R;
cin >> L >> R;
updateSpray(1, 1, N, L, R);
}
//Queries
else
{
int L, R;
cin >> L >> R;
if (b) cout << '\n';
b = true;
cout << query(1, 1, N, L, R);
}
}
}
