#include <bits/stdc++.h>
using namespace std;

#define _ << " _ " <<
#define TRACE(x) cout << #x << " = " << x << endl

typedef long long ll;

const int MaxN = 1e5 + 10, Off = 1 << 17;
int n, q, k;

struct SegTree {
    vector<ll> v[2 * Off];
    ll sum[2 * Off];
    int lazy[2 * Off];

    void update_sum(int i) {
        if (k == 1) {
            sum[i] = sum[2 * i] + sum[2 * i + 1];
            return;
        }

        sum[i] = 0;
        ll w = 1;

        for (ll x : v[i]) {
            sum[i] += x * w;
            w *= k;
        }
    }

    void propagate(int i) {
        if (k == 1) return;

        if (lazy[i] == 0) return;

        v[i].erase(v[i].begin(), v[i].begin() + min(lazy[i], (int)v[i].size()));

        update_sum(i);

        if (i >= Off) {
            lazy[i] = 0;
            return;
        }

        lazy[2 * i] += lazy[i];
        lazy[2 * i + 1] += lazy[i];

        lazy[i] = 0;
    }

    void update(int i) {
        if (k == 1) {
            update_sum(i);
            return;
        }

        v[i].resize(max(v[2 * i].size(), v[2 * i + 1].size()));

        for (int j = 0; j < (int)v[i].size(); j++) {
            v[i][j] = 0;
            if (j < (int)v[2 * i].size()) v[i][j] += v[2 * i][j];
            if (j < (int)v[2 * i + 1].size()) v[i][j] += v[2 * i + 1][j];
        }

        update_sum(i);
    }

    void update_leaf(int j, int val, int i = 1, int lo = 0, int hi = Off) {
        propagate(i);

        if (j < lo || hi <= j) return;

        if (j + Off == i) {
            sum[i] = val;
            if (k == 1) return;

            v[i].resize(0);
            while (val > 0) {
                v[i].push_back(val % k);
                val /= k;
            }
        } else {
            int mid = (lo + hi) / 2;
            update_leaf(j, val, 2 * i, lo, mid);
            update_leaf(j, val, 2 * i + 1, mid, hi);

            update(i);
        }
    }

    void update_interval(int l, int r, int i = 1, int lo = 0, int hi = Off) {
        propagate(i);

        if (r <= lo || hi <= l) return;

        if (l <= lo && hi <= r) {
            lazy[i] = 1;
            propagate(i);
        } else {
            int mid = (lo + hi) / 2;
            update_interval(l, r, 2 * i, lo, mid);
            update_interval(l, r, 2 * i + 1, mid, hi);

            update(i);
        }
    }

    ll query(int l, int r, int i = 1, int lo = 0, int hi = Off) {
        propagate(i);

        if (r <= lo || hi <= l) return 0;
        if (l <= lo && hi <= r) return sum[i];

        int mid = (lo + hi) / 2;
        return query(l, r, 2 * i, lo, mid) + query(l, r, 2 * i + 1, mid, hi);
    }
} T;


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> q >> k;

    for (int i = 0; i < n; i++) {
        int c;
        cin >> c;

        T.update_leaf(i, c);
    }

    for (int i = 0; i < q; i++) {
        int s, t, u;
        cin >> s >> t >> u;
        t--;

        if (s == 1) T.update_leaf(t, u);
        if (s == 2) T.update_interval(t, u);
        if (s == 3) cout << T.query(t, u) << "\n";
    }

    return 0;
}