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;
namespace A {
int sgn(int64_t val) { return val ? val < 0 ? -1 : 1 : 0; }
void solve() {
  int n, k;
  int64_t x;
  scanf("%d%d%" PRId64, &n, &k, &x);
  vector<int64_t> v(n);
  for (int64_t& it : v) scanf("%" PRId64, &it);
  int zer = 0;
  for (int64_t& it : v) zer += !it;
  if (zer > k) {
    for (int64_t& it : v) printf("%" PRId64 " ", it);
    printf("\n");
    return;
  }
  if (zer) {
    for (int i = 0; i < n; ++i)
      if (v[i] == 0) {
        if (zer == 1) {
          zer = i;
          break;
        }
        v[i] += x, --k, --zer;
      }
  } else
    zer = -1;
  bool neg = false;
  for (int64_t& it : v) neg ^= (it < 0);
  if (zer != -1) {
    --k;
    v[zer] += x * (neg ? 1 : -1);
    neg = true;
  }
  if (!neg) {
    int ansi = 0;
    for (int i = 1; i < n; ++i)
      if (abs(v[i]) < abs(v[ansi])) ansi = i;
    int sign = sgn(v[ansi]);
    while (k && sgn(v[ansi]) * sign != -1) v[ansi] -= sign * x, --k;
    if (sgn(v[ansi]) * sign == -1) neg ^= true;
  }
  if (neg) {
    set<pair<int64_t, int> > vs;
    for (int i = 0; i < n; ++i) vs.insert({abs(v[i]), i});
    while (k) {
      int it = vs.begin()->second;
      vs.erase(vs.begin());
      v[it] += sgn(v[it]) * x;
      vs.insert({abs(v[it]), it});
      --k;
    }
  }
  for (int64_t& it : v) printf("%" PRId64 " ", it);
  printf("\n");
}
}  // namespace A
int main() {
  A::solve();
  return 0;
}
