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 __print(int x) { cerr << x; }
void __print(long x) { cerr << x; }
void __print(long long x) { cerr << x; }
void __print(unsigned x) { cerr << x; }
void __print(unsigned long x) { cerr << x; }
void __print(unsigned long long x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char *x) { cerr << '\"' << x << '\"'; }
void __print(const string &x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }
template <typename T, typename V>
void __print(const pair<T, V> &x) {
  cerr << '{';
  __print(x.first);
  cerr << ',';
  __print(x.second);
  cerr << '}';
}
template <typename T>
void __print(const T &x) {
  int f = 0;
  cerr << '{';
  for (auto &i : x) cerr << (f++ ? "," : ""), __print(i);
  cerr << "}";
}
void _print() { cerr << "]\n"; }
template <typename T, typename... V>
void _print(T t, V... v) {
  __print(t);
  if (sizeof...(v)) cerr << ", ";
  _print(v...);
}
long long binpow(long long x, long long y) {
  long long res = 1;
  while (y > 0) {
    if (y & 1) res = (res * x);
    y = y >> 1;
    x = (x * x);
  }
  return res;
}
long long binpowmod(long long x, long long y, long long p) {
  long long res = 1;
  x = x % p;
  while (y > 0) {
    if (y & 1) res = (res * x) % p;
    y = y >> 1;
    x = (x * x) % p;
  }
  return res;
}
long long mod_inverse(long long n, long long p) {
  return binpowmod(n, p - 2, p);
}
long long gcd(long long x, long long y) {
  if (y == 0) return x;
  return gcd(y, x % y);
}
bool isPowerOfTwo(long long x) { return x && (!(x & (x - 1))); }
struct custom_hash {
  static uint64_t splitmix64(uint64_t x) {
    x += 0x9e3779b97f4a7c15;
    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
    return x ^ (x >> 31);
  }
  size_t operator()(uint64_t x) const {
    static const uint64_t FIXED_RANDOM =
        chrono::steady_clock::now().time_since_epoch().count();
    return splitmix64(x + FIXED_RANDOM);
  }
};
void swap(int &x, int &y) {
  int temp = x;
  x = y;
  y = temp;
}
unsigned int onesComplement(unsigned int n) {
  int number_of_bits = floor(log2(n)) + 1;
  return ((1 << number_of_bits) - 1) ^ n;
}
bool comp1(pair<int, int> x, pair<int, int> y) { return x.second < y.second; }
class cmp {
 public:
  bool operator()(pair<long long, long long> &a,
                  pair<long long, long long> &b) {
    return abs(a.first) > abs(b.first);
  }
};
void solve() {
  long long n, k, x;
  cin >> n >> k >> x;
  vector<long long> a(n);
  int cnt = 0;
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
    if (a[i] < 0) cnt++;
  }
  if (cnt % 2 == 0) {
    int j = 0;
    for (int i = 0; i < n; ++i) {
      if (abs(a[i]) / x + 1 == abs(a[j]) / x + 1) {
        if (abs(a[i]) < abs(a[j])) j = i;
      } else if (abs(a[i]) / x + 1 < abs(a[j]) / x + 1) {
        j = i;
      }
    }
    if (abs(a[j]) / x + 1 <= k) {
      long long tim = abs(a[j]) / x + 1;
      if (a[j] < 0) {
        a[j] += tim * x;
      } else {
        a[j] -= tim * x;
      }
      k -= tim;
    } else {
      int j = 0;
      for (int i = 0; i < n; ++i) {
        if (abs(a[i]) < abs(a[j])) j = i;
      }
      if (a[j] < 0) {
        a[j] += k * x;
      } else {
        a[j] -= k * x;
      }
      for (long long &x : a) cout << x << ' ';
      return;
    }
  }
  priority_queue<pair<long long, long long>, vector<pair<long long, long long>>,
                 cmp>
      pq;
  for (int i = 0; i < n; ++i) pq.push({a[i], i});
  while (k > 0) {
    auto top = pq.top();
    pq.pop();
    if (top.first >= 0)
      top.first += x;
    else
      top.first -= x;
    a[top.second] = top.first;
    pq.push(top);
    k--;
  }
  for (long long &x : a) cout << x << ' ';
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout << fixed << setprecision(15);
  solve();
}
