Recently Maxim has found an array of n integers, needed by no one. He immediately come up with idea of changing it: he invented positive integer x and decided to add or subtract it from arbitrary array elements. Formally, by applying single operation Maxim chooses integer i (1 ≤ i ≤ n) and replaces the i-th element of array ai either with ai + x or with ai - x. Please note that the operation may be applied more than once to the same position.

Maxim is a curious minimalis, thus he wants to know what is the minimum value that the product of all array elements (i.e. <image>) can reach, if Maxim would apply no more than k operations to it. Please help him in that.

Input

The first line of the input contains three integers n, k and x (1 ≤ n, k ≤ 200 000, 1 ≤ x ≤ 109) — the number of elements in the array, the maximum number of operations and the number invented by Maxim, respectively.

The second line contains n integers a1, a2, ..., an (<image>) — the elements of the array found by Maxim.

Output

Print n integers b1, b2, ..., bn in the only line — the array elements after applying no more than k operations to the array. In particular, <image> should stay true for every 1 ≤ i ≤ n, but the product of all array elements should be minimum possible.

If there are multiple answers, print any of them.

Examples

Input

5 3 1
5 4 3 5 2


Output

5 4 3 5 -1 


Input

5 3 1
5 4 3 5 5


Output

5 4 0 5 5 


Input

5 3 1
5 4 4 5 5


Output

5 1 4 5 5 


Input

3 2 7
5 4 2


Output

5 11 -5 
#include <bits/stdc++.h>
using namespace std;
long long const mod = 998244353;
long long const inf = 1e15;
long long n, m, k, x;
long long w[200004], ans[200004];
pair<long long, long long> t[800003];
void build(long long nd, long long l, long long r) {
  if (l == r) {
    t[nd] = {w[l], l};
    return;
  }
  long long mid = (l + r) / 2;
  build(2 * nd, l, mid);
  build(2 * nd + 1, mid + 1, r);
  if (t[2 * nd].first <= t[2 * nd + 1].first)
    t[nd] = t[2 * nd];
  else
    t[nd] = t[2 * nd + 1];
}
void up(long long nd, long long l, long long r, long long a, long long b) {
  if (a > r || a < l) return;
  if (l == r) {
    t[nd] = {b, a};
    return;
  }
  long long mid = (l + r) / 2;
  up(2 * nd, l, mid, a, b);
  up(2 * nd + 1, mid + 1, r, a, b);
  if (t[2 * nd].first <= t[2 * nd + 1].first)
    t[nd] = t[2 * nd];
  else
    t[nd] = t[2 * nd + 1];
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> k >> x;
  long long d1 = 0, d2 = 0;
  long long mn = 0, mx = n + 1;
  w[0] = inf;
  w[n + 1] = -inf;
  long long v = -1;
  for (int i = 1; i <= n; i++) {
    cin >> w[i];
    if (w[i] == 0) {
      if (v == -1)
        v = i;
      else {
        if (k) {
          w[i] -= x;
          k--;
        }
      }
    }
    if (w[i] > 0) {
      d1++;
      if (w[i] < w[mn]) mn = i;
    } else if (w[i] < 0) {
      d2++;
      if (w[i] > w[mx]) mx = i;
    }
  }
  if (v != -1 && k) {
    if (d2 % 2)
      w[v] = x;
    else
      w[v] = -x, d2++;
    k--;
  }
  if (d2 % 2 == 0) {
    long long dd1, dd2;
    dd1 = dd2 = 1e9;
    if (d1) dd1 = w[mn] / x + 1;
    if (d2) dd2 = (abs(w[mx])) / x + 1;
    if ((dd1 == dd2 && (x - w[mn] % x) >= (x - (abs(w[mx])) % x)) ||
        (dd1 < dd2)) {
      w[mn] -= min(dd1, k) * x;
      k -= min(dd1, k);
    } else {
      w[mx] += min(dd2, k) * x;
      k -= min(dd2, k);
    }
  }
  for (int i = 1; i <= n; i++) ans[i] = w[i], w[i] = abs(w[i]);
  build(1, 1, n);
  for (int ff = 1; ff <= k; ff++) {
    pair<long long, long long> d = t[1];
    if (ans[d.second] > 0)
      ans[d.second] += x;
    else
      ans[d.second] -= x;
    up(1, 1, n, d.second, abs(ans[d.second]));
  }
  for (int i = 1; i <= n; i++) cout << ans[i] << ' ';
  return 0;
}
