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;
int break_point() {
  char c;
  while ((c = getchar()) != '\n')
    ;
  return 0;
}
template <typename T>
void read_integer(T &r) {
  bool sign = 0;
  r = 0;
  char c;
  while (1) {
    c = getchar();
    if (c == '-') {
      sign = 1;
      break;
    }
    if (c != ' ' && c != '\n') {
      r = c - '0';
      break;
    }
  }
  while (1) {
    c = getchar();
    if (c == ' ' || c == '\n') break;
    r = r * 10 + (c - '0');
  }
  if (sign) r = -r;
}
long long binpowmod(long long a, long long b, long long mod) {
  if (b == 0) return 1;
  long long c = binpowmod(a, b >> 1, mod);
  return (((c * c) % mod) * (b & 1 ? a : 1)) % mod;
}
long long binpow(long long a, long long b) {
  if (b == 0) return 1;
  long long c = binpow(a, b >> 1);
  return c * c * (b & 1 ? a : 1);
}
inline int getbit(int x, int b) { return (x >> b) & 1; }
inline int setbit(int x, int b) { return x | (1 << b); }
inline void _setbit(int &x, int b) { x = setbit(x, b); }
inline long long setbit(long long x, int b) { return x | (1ll << b); }
inline void _setbit(long long &x, int b) { x = setbit(x, b); }
inline int unsetbit(int x, int b) { return x & (INT_MAX - (1 << b)); }
inline void _unsetbit(int &x, int b) { x = unsetbit(x, b); }
inline int countbit(int x) {
  x = x - ((x >> 1) & 0x55555555);
  x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
  return ((x + (x >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
}
inline long long countbit(long long x) {
  return countbit(int(x & INT_MAX)) + countbit(int(x >> 32) & INT_MAX);
}
inline void printbit(int x, int len) {
  for (int i = len - 1; i >= 0; i--) printf("%d", getbit(x, i));
}
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
template <typename A, typename B>
ostream &operator<<(ostream &stream, const pair<A, B> &p) {
  stream << "{" << p.first << "," << p.second << "}";
  return stream;
}
template <typename A>
ostream &operator<<(ostream &stream, const vector<A> &v) {
  stream << "[";
  for (auto itr = v.begin(); itr != v.end(); itr++) stream << *itr << " ";
  stream << "]";
  return stream;
}
template <typename A, typename B>
ostream &operator<<(ostream &stream, const map<A, B> &v) {
  stream << "[";
  for (auto itr = v.begin(); itr != v.end(); itr++) stream << *itr << " ";
  stream << "]";
  return stream;
}
template <typename A>
ostream &operator<<(ostream &stream, const set<A> &v) {
  stream << "[";
  for (auto itr = v.begin(); itr != v.end(); itr++) stream << *itr << " ";
  stream << "]";
  return stream;
}
template <typename A>
ostream &operator<<(ostream &stream, const stack<A> &v) {
  stack<A> st = v;
  stream << "[";
  while (!st.empty()) {
    stream << st.top() << " ";
    st.pop();
  }
  stream << "]";
  return stream;
}
template <typename A>
ostream &operator<<(ostream &stream, const priority_queue<A> &v) {
  priority_queue<A> q = v;
  stream << "[";
  while (!q.empty()) {
    stream << q.top() << " ";
    q.pop();
  }
  stream << "]";
  return stream;
}
template <typename A>
ostream &operator<<(ostream &stream, const queue<A> &v) {
  queue<A> q = v;
  stream << "[";
  while (!q.empty()) {
    stream << q.front() << " ";
    q.pop();
  }
  stream << "]";
  return stream;
}
template <typename A>
ostream &operator<<(ostream &stream, const deque<A> &v) {
  deque<A> q = v;
  stream << "[";
  while (!q.empty()) {
    stream << q.front() << " ";
    q.pop_front();
  }
  stream << "]";
  return stream;
}
void run();
int main() {
  srand(time(NULL));
  run();
  return 0;
}
const int mod = 1e9 + 7;
const int N = 200005;
int a[N];
long long b[N];
bool neg[N];
struct item {
  long long val;
  int idx;
  item(int _val, int _idx) : val(_val), idx(_idx) {}
  bool operator<(const item &other) const {
    if (abs(val) == abs(other.val)) return idx < other.idx;
    return abs(val) < abs(other.val);
  }
};
int bs(long long t, int x) {
  int l = 1, r = 1000000000;
  int ret = 0;
  while (l <= r) {
    int mid = (l + r) >> 1;
    if (t - x * 1ll * mid < 0)
      ret = mid, r = mid - 1;
    else
      l = mid + 1;
  }
  0 ? (cout << "t"
            << " = " << (t) << ","
            << "x"
            << " = " << (x) << ","
            << "ret"
            << " = " << (ret) << "\n")
    : cout;
  return ret;
}
void run() {
  int n, k, x;
  scanf("%d%d%d", &n, &k, &x);
  set<item> st[2];
  for (int i = 0; i < n; ++i) {
    scanf("%d", &a[i]);
    st[a[i] >= 0].insert(item(a[i], i));
  }
  bool odd_neg = false;
  if (((int)st[0].size()) & 1) {
    odd_neg = true;
    st[1].insert(st[0].begin(), st[0].end());
  } else {
    if (!st[1].empty() &&
        (st[0].empty() || (*st[1].begin()) < (*st[0].begin()))) {
      item it = *st[1].begin();
      0 ? (cout << "it.val + 1 - 1"
                << " = " << (it.val + 1 - 1) << "\n")
        : cout;
      st[1].erase(st[1].begin());
      long long t = it.val;
      int cnt = bs(t, x);
      0 ? (cout << "cnt"
                << " = " << (cnt) << ","
                << "t"
                << " = " << (t) << ","
                << "x"
                << " = " << (x) << "\n")
        : cout;
      if (cnt <= k) {
        it.val -= cnt * 1ll * x;
        0 ? (cout << "it.val"
                  << " = " << (it.val) << "\n")
          : cout;
        k -= cnt;
        odd_neg = true;
      }
      st[1].insert(it);
    } else {
      item it = (*st[0].begin());
      st[0].erase(st[0].begin());
      long long t = abs(it.val);
      int cnt = bs(t, x);
      if (cnt <= k) {
        it.val += x * 1ll * cnt;
        0 ? (cout << "it.val"
                  << " = " << (it.val) << "\n")
          : cout;
        k -= cnt;
        odd_neg = true;
      }
      st[0].insert(it);
    }
    st[1].insert(st[0].begin(), st[0].end());
  }
  0 ? (cout << "odd_neg"
            << " = " << (odd_neg) << "\n")
    : cout;
  while (k--) {
    item i = (*st[1].begin());
    st[1].erase(st[1].begin());
    0 ? (cout << "i.val"
              << " = " << (i.val) << "\n")
      : cout;
    if (odd_neg) {
      if (i.val < 0)
        i.val -= x;
      else
        i.val += x;
    } else {
      if (i.val > 0)
        i.val -= x;
      else
        i.val += x;
    }
    st[1].insert(i);
  }
  for (item i : st[1]) b[i.idx] = i.val;
  for (int i = 0; i < n; ++i, putchar(' ')) printf("%lld", b[i]);
  putchar('\n');
}
