// trans rights
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int N, Q, K;
constexpr int H = 39;
struct Package
{
ll P[H];
void roll()
{
if (K == 1)
return;
for (int i = 0; i < H - 1; i++)
P[i] = P[i + 1];
P[H - 1] = 0;
}
};
Package combine(const Package& a, const Package& b)
{
Package c;
for (int i = 0; i < H; i++)
c.P[i] = a.P[i] + b.P[i];
return c;
}
struct Node
{
int l, r;
Node *lc, *rc;
int rolln = 0;
Package pk;
Node(int l, int r) : l(l), r(r), lc(0), rc(0)
{
if (l != r)
{
int m = l + (r - l) / 2;
lc = new Node(l, m);
rc = new Node(m + 1, r);
}
}
void clean()
{
for (int k = 0; k < rolln; k++)
pk.roll();
if (l != r)
{
lc->rolln += rolln;
rc->rolln += rolln;
}
rolln = 0;
}
void update(int p, int x)
{
clean();
if (l == r)
{
pk.P[0] = x;
for (int i = 1; i < H; i++)
pk.P[i] = pk.P[i - 1] / K;
return;
}
if (p <= lc->r)
{
lc->update(p, x);
rc->clean();
}
else{
rc->update(p, x);
lc->clean();
}
pk = combine(lc->pk, rc->pk);
}
void spray(int ql, int qr)
{
clean();
if (qr < l or ql > r)
return;
if (ql <= l and qr >= r)
{
rolln++;
clean();
return;
}
lc->spray(ql, qr);
rc->spray(ql, qr);
pk = combine(lc->pk, rc->pk);
}
ll query(int ql, int qr)
{
clean();
if (qr < l or ql > r)
return 0;
if (ql <= l and qr >= r)
return pk.P[0];
return lc->query(ql, qr) + rc->query(ql, qr);
}
};
int main(int argc, const char *argv[])
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N >> Q >> K;
Node *root = new Node(1, N);
for (int i = 1; i <= N; i++)
{
int a;
cin >> a;
root->update(i, a);
}
for (int k = 0; k < Q; k++)
{
int s, t, u;
cin >> s >> t >> u;
if (s == 1)
{
root->update(t, u);
}else if (s == 2)
{
root->spray(t, u);
}else if(s == 3)
{
cout << root->query(t, u) << '\n';
}
}
return 0;
}
