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;
void fre() {
  freopen("c://test//input.in", "r", stdin);
  freopen("c://test//output.out", "w", stdout);
}
template <class T1, class T2>
inline void gmax(T1 &a, T2 b) {
  if (b > a) a = b;
}
template <class T1, class T2>
inline void gmin(T1 &a, T2 b) {
  if (b < a) a = b;
}
const int N = 2e5 + 10, M = 0, Z = 1e9 + 7, inf = 0x3f3f3f3f;
template <class T1, class T2>
inline void gadd(T1 &a, T2 b) {
  a = (a + b) % Z;
}
int casenum, casei;
int n, K, X;
long long a[N];
struct node {
  long long x;
  int sg;
  int p;
  bool operator<(const node &b) const {
    if (abs(x) != abs(b.x)) return abs(x) < abs(b.x);
    return p < b.p;
  }
};
set<node> sot;
int main() {
  while (~scanf("%d%d%d", &n, &K, &X)) {
    sot.clear();
    int neg = 0;
    for (int i = 1; i <= n; ++i) {
      int x;
      scanf("%d", &x);
      int sg = (x >= 0 ? 1 : -1);
      if (x < 0) ++neg;
      sot.insert({x, sg, i});
    }
    if (neg % 2 == 0) {
      while (K) {
        --K;
        long long x = sot.begin()->x;
        int sg = sot.begin()->sg;
        int p = sot.begin()->p;
        sot.erase(sot.begin());
        if ((x - X * sg) * sg <= 0) {
          sot.insert({x - X * sg, -sg, p});
          break;
        } else {
          sot.insert({x - X * sg, sg, p});
        }
      }
    }
    while (K) {
      --K;
      long long x = sot.begin()->x;
      int sg = sot.begin()->sg;
      int p = sot.begin()->p;
      sot.erase(sot.begin());
      sot.insert({x + X * sg, sg, p});
    }
    for (auto it : sot) a[it.p] = it.x;
    for (int i = 1; i <= n; ++i) printf("%I64d ", a[i]);
    puts("");
  }
  return 0;
}
