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 int Maxn = 200000;
int n;
long long k, T;
long long num[Maxn + 5];
long long ff[Maxn + 5];
struct Btree {
  int left, right;
  long long min;
  int pos;
};
Btree tree[Maxn * 4 + 5];
inline void update(int x) {
  if (tree[x].left == tree[x].right) return;
  if (tree[x * 2].min < tree[x * 2 + 1].min) {
    tree[x].min = tree[x * 2].min;
    tree[x].pos = tree[x * 2].pos;
  } else {
    tree[x].min = tree[x * 2 + 1].min;
    tree[x].pos = tree[x * 2 + 1].pos;
  }
}
inline void build(int x, int left, int right) {
  tree[x].left = left;
  tree[x].right = right;
  if (left == right) {
    tree[x].min = num[left];
    tree[x].pos = left;
  } else {
    int mid = (left + right) / 2;
    build(x * 2, left, mid);
    build(x * 2 + 1, mid + 1, right);
    update(x);
  }
}
void addTree(int x, int pos, int val) {
  if (tree[x].left == tree[x].right) {
    tree[x].min += val;
  } else {
    int mid = (tree[x].left + tree[x].right) / 2;
    if (pos <= mid) addTree(x * 2, pos, val);
    if (mid + 1 <= pos) addTree(x * 2 + 1, pos, val);
    update(x);
  }
}
inline long long judge(long long mid) {
  long long ret = 0;
  for (int i = 1; i <= n; i++) {
    if (num[i] < mid)
      ret = ret + (num[i] - mid) / k + ((num[i] - mid) % k == 0 ? 0 : 1);
  }
  return ret;
}
inline void maxPossible() {
  if (T == 0) return;
  for (int i = 1; i <= n; i++) {
    if (num[i] < 0) {
      ff[i] = -1;
      num[i] = -num[i];
    } else {
      ff[i] = 1;
    }
  }
  build(1, 1, n);
  for (int rt = 1; rt <= T; rt++) {
    int minPos = tree[1].pos;
    num[minPos] += k;
    addTree(1, minPos, k);
  }
  for (int i = 1; i <= n; i++) num[i] = num[i] * ff[i];
}
int main() {
  scanf("%d%I64d%I64d", &n, &T, &k);
  for (int i = 1; i <= n; i++) scanf("%I64d", &num[i]);
  int flagF = 0, flagZ = 0;
  for (int i = 1; i <= n; i++) {
    if (num[i] == 0) flagZ++;
    if (num[i] < 0) flagF++;
  }
  if (flagZ > T) {
    for (int i = 1; i <= n; i++) {
      if (num[i] == 0 && T > 0) {
        num[i] -= k;
        T--;
      }
      if (i == n)
        printf("%I64d\n", num[i]);
      else
        printf("%I64d ", num[i]);
    }
    return 0;
  }
  if (flagZ > 0) {
    if (flagF & 1) {
      for (int i = 1; i <= n; i++)
        if (num[i] == 0) {
          num[i] += k;
          T--;
        }
    } else {
      bool flag = true;
      for (int i = 1; i <= n; i++)
        if (num[i] == 0) {
          if (flag) {
            num[i] -= k;
            flag = false;
          } else {
            num[i] += k;
          }
          T--;
        }
    }
    maxPossible();
    for (int i = 1; i <= n; i++)
      if (i == n)
        printf("%I64d\n", num[i]);
      else
        printf("%I64d ", num[i]);
    return 0;
  }
  if (flagF & 1) {
    maxPossible();
    for (int i = 1; i <= n; i++)
      if (i == n)
        printf("%I64d\n", num[i]);
      else
        printf("%I64d ", num[i]);
    return 0;
  }
  int maxFPos = -1, minZPos = -1;
  for (int i = 1; i <= n; i++) {
    if (num[i] > 0) {
      if (minZPos == -1 || num[minZPos] > num[i]) minZPos = i;
    } else {
      if (maxFPos == -1 || num[maxFPos] < num[i]) maxFPos = i;
    }
  }
  if (maxFPos == -1) num[maxFPos = 200001] = -1e9 - 1;
  if (minZPos == -1) num[minZPos = 200001] = 1e9 + 1;
  long long delta = min(-num[maxFPos], num[minZPos]);
  if (delta / k + 1 <= T) {
    if (-num[maxFPos] > num[minZPos]) {
      num[minZPos] -= (delta / k + 1) * k;
      T -= delta / k + 1;
    } else {
      num[maxFPos] += (delta / k + 1) * k;
      T -= delta / k + 1;
    }
    maxPossible();
    for (int i = 1; i <= n; i++)
      if (i == n)
        printf("%I64d\n", num[i]);
      else
        printf("%I64d ", num[i]);
    return 0;
  } else {
    if (-num[maxFPos] > num[minZPos]) {
      num[minZPos] -= T * k;
    } else {
      num[maxFPos] += T * k;
    }
    for (int i = 1; i <= n; i++)
      if (i == n)
        printf("%I64d\n", num[i]);
      else
        printf("%I64d ", num[i]);
    return 0;
  }
  maxPossible();
  for (int i = 1; i <= n; i++)
    if (i == n)
      printf("%I64d\n", num[i]);
    else
      printf("%I64d ", num[i]);
  return 0;
}
