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;
const double eps = 1e-10;
const int maxn = 2e5 + 10;
const long long INF = 2e9;
long long n, k, x;
long long a[maxn];
long long aa[maxn];
long long ans[maxn];
struct no {
  int id;
  long long ab;
  bool operator<(const no& c) const { return ab < c.ab; }
};
multiset<no> s;
int cnt = 0;
inline int dcmp(long long x) {
  if (!x) return 0;
  return x > 0 ? 1 : -1;
}
int dd = 0;
void tr() {
  for (int t = (0); t < (n); ++t) s.insert(no{t, abs(a[t])});
  for (int t = (0); t < (k); ++t) {
    no c = *s.begin();
    s.erase(s.begin());
    s.insert(no{c.id, c.ab + x});
  }
  cnt += k;
  for (auto r : s) {
    ans[r.id] = r.ab * dcmp(a[r.id]);
  }
}
void tr2() {
  for (int t = (0); t < (n); ++t) s.insert(no{t, abs(a[t])});
  for (int t = (0); t < (k); ++t) {
    no c = *s.begin();
    s.erase(s.begin());
    s.insert(no{c.id, c.ab - x});
  }
  cnt += k;
  for (auto r : s) {
    ans[r.id] = r.ab * dcmp(a[r.id]);
  }
}
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n >> k >> x;
  int kk = k;
  for (int t = (0); t < (n); ++t) cin >> a[t], aa[t] = abs(a[t]);
  int beg = 1;
  for (int t = (0); t < (n); ++t) beg *= dcmp(a[t]);
  if (beg < 0) {
    tr();
  } else {
    if (beg == 0) {
      int c0 = 0;
      for (int t = (0); t < (n); ++t) c0 += (a[t] == 0);
      int cc0 = c0;
      if (c0 > k)
        for (int t = (0); t < (n); ++t) ans[t] = a[t];
      else {
        int e = 1;
        for (int t = (0); t < (n); ++t)
          if (dcmp(a[t])) e *= dcmp(a[t]);
        for (int t = (0); t < (n); ++t) {
          if (!a[t]) {
            if (!--c0) {
              if (e == 1)
                a[t] -= x;
              else
                a[t] = x;
            } else
              a[t] += x;
          }
        }
        k -= cc0;
        cnt += cc0;
        tr();
      }
    } else {
      long long mi = INF;
      for (int t = (0); t < (n); ++t) mi = min(mi, aa[t]);
      if (mi >= k * x) {
        tr2();
      } else {
        for (int t = (0); t < (n); ++t) {
          if (aa[t] == mi) {
            while (aa[t] >= 0) aa[t] -= x, --k, ++cnt;
            a[t] = dcmp(a[t]) * aa[t];
            aa[t] = abs(aa[t]);
            break;
          }
        }
        tr();
      }
    }
  }
  assert(cnt <= kk);
  for (int t = (0); t < (n); ++t) dd += (abs(ans[t] - a[t]) / x);
  assert(dd <= kk);
  for (int t = (0); t < (n); ++t) cout << ans[t] << " ";
}
