#include <bits/stdc++.h>
using namespace std;
#define name ""
#define int long long
const int N = 5e5 + 7;
int n, q, k, a[N];
struct Node{
basic_string<int>val;
Node() {}
Node(int x) {
// Code here
while(x > 0){
val += (x % k);
x /= k;
}
}
Node(Node l, Node r) {
// Code here
for(int i = 0 ; i < (int)max(l.val.size() , r.val.size()); i++)
val += (i < (int)l.val.size() ? l.val[i] : 0 ) + (i < (int)r.val.size() ? r.val[i] : 0);
}
explicit operator long long() {
long long res = 0;
reverse(val.begin(), val.end());
for (int i : val) res = res * k + i;
reverse(val.begin(), val.end());
return res;
}
} st[N << 2];
struct Update {
int cnt_div = 0;
Update() {}
Update(int x) : cnt_div(x) {}
Update(Update l, Update r) {
cnt_div = l.cnt_div + r.cnt_div;
}
} lazy[N << 2];
Node identity_value() { return Node(); }
Node merge(Node a, Node b) { return Node(a, b); }
Update identity_update() { return Update(); }
Node apply_update(Update v, Node x) {
// Code here
// for(int i = 0 ; i < v.cnt_div ; i++){
// if(!x.val.empty()) x.val.erase(x.val.begin());
// }
Node res;
for (int i = v.cnt_div; i < (int)x.val.size(); i++)
res.val += x.val[i];
return res;
}
Update merge_update(Update a, Update b) { return Update(a, b); }
void recalc(int id) {
st[id] = merge(st[id << 1], st[id << 1 | 1]);
}
void build(int id = 1, int l = 1, int r = n) {
// Code here
if (l == r) return st[id] = Node(a[l]), void();
int mid = (l + r) >> 1;
build(id << 1, l, mid);
build(id << 1 | 1, mid + 1, r);
recalc(id);
}
void apply(int id, Update upd) {
st[id] = apply_update(upd, st[id]);
lazy[id] = merge_update(lazy[id], upd);
}
void down(int id) {
apply(id << 1, lazy[id]), apply(id << 1 | 1, lazy[id]);
lazy[id] = identity_update();
}
Node query(int u, int v, int id = 1, int l = 1, int r = n) {
if (v < l || u > r) return identity_value();
if (u <= l && r <= v) return st[id];
down(id);
int mid = (l + r) >> 1;
return merge(query(u, v, id << 1, l, mid), query(u, v, id << 1 | 1, mid + 1, r));
}
void update(int u, int v, Update upd, int id = 1, int l = 1, int r = n) {
if (v < l || u > r) return;
if (u <= l && r <= v) return apply(id, upd);
down(id);
int mid = (l + r) >> 1;
update(u, v, upd, id << 1, l, mid);
update(u, v, upd, id << 1 | 1, mid + 1, r);
recalc(id);
}
void assign(int p, int v, int id = 1, int l = 1, int r = n) {
if (l == r) return st[id] = Node(v), void();
down(id);
int mid = (l + r) >> 1;
if (p <= mid) assign(p, v, id << 1, l, mid);
else assign(p, v, id << 1 | 1, mid + 1, r);
recalc(id);
}
namespace k_1{
long long st[N << 2];
void build(int id = 1 , int l = 1 , int r = n){
if(l == r) return st[id] = a[l], void();
int mid = (l + r ) >> 1;
build(id << 1, l , mid);
build(id << 1 | 1 , mid + 1 , r);
st[id] = st[id << 1] + st[id << 1 | 1];
}
void update(int p , int v, int id = 1 , int l = 1 , int r = n){
if (l == r) return st[id] = v , void();
int mid = (l + r) >> 1;
if(p <= mid) update(p , v, id << 1, l , mid );
else update(p , v, id << 1 | 1, mid + 1 , r);
st[id] = st[id << 1] + st[id << 1 | 1];
}
long long query(int u, int v, int id = 1, int l = 1, int r = n) {
if (v < l || u > r) return 0;
if (u <= l && r <= v) return st[id];
// down(id);
int mid = (l + r) >> 1;
return (query(u, v, id << 1, l, mid) +query(u, v, id << 1 | 1, mid + 1, r));
}
}
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
if(fopen("bug.inp", "r"))
freopen("bug.inp", "r", stdin), freopen("bug.out", "w", stdout);
else if (fopen(name".inp", "r"))
freopen(name".inp", "r", stdin), freopen(name".out", "w", stdout);
cin >> n >> q >> k;
for (int i = 1; i <= n; i++) cin >> a[i];
if (k == 1) {
k_1::build();
while (q--) {
int t, u, v; cin >> t >> u >> v;
if (t == 1) k_1::update(u, v);
if (t == 3) cout << k_1::query(u, v) << '\n';
}
return 0;
}
build();
while (q--) {
int t, u, v; cin >> t >> u >> v;
if (t == 1) assign(u, v);
if (t == 2) update(u, v, Update(1));
if (t == 3) cout << (long long)query(u, v) << '\n';
}
return 0;
}
