#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;

auto seed = std::chrono::steady_clock::now().time_since_epoch().count();
mt19937 rnd(seed);

using ll = long long;

#define int ll

using vi = vector<int>;
using pii = pair<int, int>;
using vp = vector<pair<int, int>>;
using vv = vector<vector<int>>;

template<class T>
using ordered_set = __gnu_pbds::tree<T, __gnu_pbds::null_type, less<T>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>;

vi f(int m, int k, vi a) {
    a.push_back(-1e18);
    for (; m > 0;) {
        std::sort(a.rbegin(), a.rend());
        if (a[k - 1] - a[k] + 1 >= m) {
            for (int i = 0; i < k; ++i) {
                a[i] -= m;
            }
            m = 0;
        } else {
            int d = a[k - 1] - a[k] + 1;
            for (int i = 0; i < k; ++i) {
                a[i] -= d;
            }
            m -= d;
        }
    }
    std::sort(a.rbegin(), a.rend());
    a.pop_back();
    std::reverse(a.begin(), a.end());
    return a;
}

void solve() {
    int n, m0, k0, q;
    cin >> n >> m0 >> k0 >> q;
    vi a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    auto a0 = f(m0, k0, a);
    for (int i = 0; i < n; ++i) {
        cout << a0[i] << ' ';
    }
    cout << '\n';
    for (int i = 0; i < q; ++i) {
        int t;
        cin >> t;
        if (t == 1) {
            int m, k, x;
            cin >> m >> k >> x;
            cout << f(m, k, a)[x - 1] << '\n';

        }
        if (t == 2) {
            int p, v;
            cin >> p >> v;
            a[p - 1] = v;
        }
        if (t == 3) {
            int m, k, l, r;
            cin >> m >> k >> l >> r;
            auto b = f(m, k, a);
            ll an = 0;
            for (int j = l - 1; j < r; ++j) {
                an += b[j];
            }
            cout << an << '\n';
        }
    }
}

signed main() {
#ifdef LOCAL
    freopen("C:\\work\\untitled\\input.txt", "r", stdin);
    freopen("C:\\work\\untitled\\output.txt", "w", stdout);
    auto start = std::chrono::steady_clock::now();
#else
    cin.tie();
    cout.tie();
    ios_base::sync_with_stdio(0);
#endif
    int t_ = 1;
    //cin>>t;
    while (t_--) {
        solve();
    }

#ifdef LOCAL
    auto end = std::chrono::steady_clock::now();
    cout << "\n======\n";
    cout << chrono::duration_cast<chrono::milliseconds>(end - start);
#endif
}
