#include <bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

constexpr int inf = 1E9;

constexpr int N = 1E7;

struct Info {
    int l = 0;
    int r = 0;
    int cnt = 0;
} t[N];
int tot = 0;
std::vector<int> recycle;

int newNode() {
    if (!recycle.empty()) {
        int x = recycle.back();
        recycle.pop_back();
        t[x] = {};
        return x;
    }
    return ++tot;
}

int merge(int a, int b) {
    if (!a) {
        return b;
    }
    if (!b) {
        return a;
    }
    
    t[a].cnt += t[b].cnt;
    t[a].l = merge(t[a].l, t[b].l);
    t[a].r = merge(t[a].r, t[b].r);
    recycle.push_back(b);
    return a;
}

void add(int &p, int l, int r, int v) {
    if (!p) {
        p = newNode();
    }
    t[p].cnt++;
    if (r - l == 1) {
        return;
    }
    int m = (l + r) / 2;
    if (v < m) {
        add(t[p].l, l, m, v);
    } else {
        add(t[p].r, m, r, v);
    }
}

int find(std::vector<int> a, int l, int r, int k) {
    int sum = 0;
    for (auto x : a) {
        sum += t[x].cnt;
    }
    if (k >= sum) {
        return r;
    }
    if (r - l == 1) {
        return l;
    }
    int m = (l + r) / 2;
    int left = 0;
    for (auto x : a) {
        left += t[t[x].l].cnt;
    }
    if (k < left) {
        for (auto &x : a) {
            x = t[x].l;
        }
        return find(std::move(a), l, m, k);
    } else {
        for (auto &x : a) {
            x = t[x].r;
        }
        return find(std::move(a), m, r, k - left);
    }
}

int split(int &p, int l, int r, int x) {
    if (l >= x || !p) {
        return 0;
    }
    if (r <= x) {
        return std::exchange(p, 0);
    }
    int m = (l + r) / 2;
    int q = newNode();
    t[q].l = split(t[p].l, l, m, x);
    t[q].r = split(t[p].r, m, r, x);
    t[q].cnt = t[t[q].l].cnt + t[t[q].r].cnt;
    t[p].cnt = t[t[p].l].cnt + t[t[p].r].cnt;
    if (!t[p].cnt) {
        recycle.push_back(p);
        p = 0;
    }
    if (!t[q].cnt) {
        recycle.push_back(q);
        q = 0;
    }
    return q;
}

void dfs(int p, int l, int r, std::vector<int> &ans, int v) {
    if (!p) {
        return;
    }
    if (r - l == 1) {
        ans[l] = v;
        return;
    }
    int m = (l + r) / 2;
    dfs(t[p].l, l, m, ans, v);
    dfs(t[p].r, m, r, ans, v);
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n, m;
    std::cin >> n >> m;
    
    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }
    
    const int A = *std::max_element(a.begin(), a.end());
    
    std::vector tr(2 * A + 1, std::vector<int>(A + 1));
    std::vector<std::array<int, 2>> big;
    
    int l = n;
    
    for (int i = n - 1; i >= 0; i--) {
        assert(big.size() <= 1);
        
        int want = 0;
        for (auto [v, i] : big) {
            want += v;
        }
        for (int a = 1; a <= A; a++) {
            for (int v = 1; v <= 2 * A; v++) {
                want += t[tr[v][a]].cnt * v;
            }
        }
        
        int need = (n - i) / 2;
        int cur = 2 * A;
        
        for (auto [v, i] : big) {
            if (need > 0) {
                want -= v;
                need--;
            }
        }
        while (cur > 0 && need > 0) {
            int layer = 0;
            for (int a = 1; a <= A; a++) {
                layer += t[tr[cur][a]].cnt;
            }
            if (layer > need) {
                break;
            }
            want -= cur * layer;
            need -= layer;
            cur--;
        }
        
        if (want - cur * need <= m) {
            int my = m - (want - cur * need);
            if ((n - i) / 2 > 0) {
                for (auto [v, i] : big) {
                    add(tr[0][a[i]], 0, n, i);
                }
                big.clear();
            }
            for (int v = 2 * A; v > cur; v--) {
                for (int a = 1; a <= A; a++) {
                    tr[0][a] = merge(tr[0][a], tr[v][a]);
                    tr[v][a] = 0;
                }
            }
            if (cur > 0 && need > 0) {
                int x = find(tr[cur], 0, n, need);
                for (int a = 1; a <= A; a++) {
                    int p = split(tr[cur][a], 0, n, x);
                    tr[0][a] = merge(tr[0][a], p);
                }
            }
            while (l > i + 1) {
                l--;
                add(tr[0][a[l]], 0, n, l);
            }
            if (my + a[i] <= 2 * A) {
                add(tr[my][a[i]], 0, n, i);
            } else {
                big.push_back({my + a[i], i});
            }
            l = i;
            for (int a = 1; a <= A; a++) {
                for (int v = 2 * A; v >= 0; v--) {
                    if (tr[v][a]) {
                        assert(v + a <= 2 * A);
                        tr[v + a][a] = tr[v][a];
                        tr[v][a] = 0;
                    }
                }
            }
        }
    }
    
    std::vector<int> ans(n, -1);
    
    for (auto [v, i] : big) {
        ans[i] = v - a[i];
    }
    for (int a = 1; a <= A; a++) {
        for (int v = a; v <= 2 * A; v++) {
            dfs(tr[v][a], 0, n, ans, v - a);
        }
    }
    
    for (int i = 0; i < n; i++) {
        std::cout << ans[i] << " \n"[i == n - 1];
    }
    
    return 0;
}