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;
inline bool SR(int &x) { return scanf("%d", &x) == 1; }
inline bool SR(long long &x) { return scanf("%lld", &x) == 1; }
inline bool SR(double &x) { return scanf("%lf", &x) == 1; }
inline bool SR(char *s) { return scanf("%s", s) == 1; }
inline bool RI() { return true; }
template <typename I, typename... T>
inline bool RI(I &x, T &...tail) {
  return SR(x) && RI(tail...);
}
inline void SP(const int x) { printf("%d", x); }
inline void SP(const long long x) { printf("%lld", x); }
inline void SP(const double x) { printf("%.16lf", x); }
inline void SP(const char *s) { printf("%s", s); }
inline void PL() { puts(""); }
template <typename I, typename... T>
inline void PL(const I x, const T... tail) {
  SP(x);
  if (sizeof...(tail)) putchar(' ');
  PL(tail...);
}
template <typename I>
void _DOING(const char *s, I &&x) {
  cerr << s << " = " << x << endl;
}
template <typename I, typename... T>
void _DOING(const char *s, I &&x, T &&...tail) {
  int c = 0;
  while (*s != ',' || c != 0) {
    if (*s == '(' || *s == '[' || *s == '{') c++;
    if (*s == ')' || *s == ']' || *s == '}') c--;
    cerr << *s++;
  }
  cerr << " = " << x << " , ";
  _DOING(s + 1, tail...);
}
inline int RAND() {
  static int x = 880301;
  return (x = x * 0xdefaced + 1) & 0x7fffffff;
}
const int MAX_N = 200000 + 10;
long long a[MAX_N];
int sc[3];
int main() {
  int N, K, X;
  RI(N, K, X);
  priority_queue<pair<long long, int>, vector<pair<long long, int> >,
                 greater<pair<long long, int> > >
      pq;
  for (int i = 0; i < int(N); i++) {
    RI(a[i]);
    if (a[i] > 0)
      sc[2]++;
    else if (a[i] == 0)
      sc[1]++;
    else
      sc[0]++;
    pq.push(make_pair(abs(a[i]), i));
  }
  while (K--) {
    int u = pq.top().second;
    pq.pop();
    int sign = 1;
    if (sc[1])
      sign = 0;
    else if (sc[0] & 1)
      sign = -1;
    if (a[u] < 0)
      sc[0]--;
    else if (a[u] == 0)
      sc[1]--;
    else
      sc[2]--;
    if (sign == 0) {
      if (sc[0] & 1)
        a[u] += X;
      else
        a[u] -= X;
    } else if (sign == 1) {
      if (a[u] < 0)
        a[u] += X;
      else
        a[u] -= X;
    } else {
      if (a[u] < 0)
        a[u] -= X;
      else
        a[u] += X;
    }
    if (a[u] < 0)
      sc[0]++;
    else if (a[u] == 0)
      sc[1]++;
    else
      sc[2]++;
    pq.push(make_pair(abs(a[u]), u));
  }
  for (int i = 0; i < N; i++) printf("%lld%c", a[i], " \n"[i == N - 1]);
  return 0;
}
