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 N, K;
signed long long X;
int A[202020];
signed long long R[202020];
vector<pair<int, int>> P, M, Z;
void solve() {
  int i, j, k, l, r, x, y;
  string s;
  cin >> N >> K >> X;
  for (i = 0; i < (N); i++) {
    cin >> A[i];
    R[i] = A[i];
    if (A[i] == 0) Z.push_back({A[i], i});
    if (A[i] < 0) M.push_back({A[i], i});
    if (A[i] > 0) P.push_back({A[i], i});
  }
  if (Z.size() > K) {
    R[Z.front().second] += K * X;
  } else {
    for (i = 0; i < (Z.size()); i++) P.push_back(Z[i]);
    sort((P.begin()), (P.end()));
    sort((M.begin()), (M.end()));
    reverse((M.begin()), (M.end()));
    if (M.size() % 2 == 0) {
      if (M.empty() ||
          (P.size() && M.size() && abs(P[0].first) <= abs(M[0].first))) {
        auto r = P[0];
        if (r.first < K * X) {
          P.erase(P.begin());
          x = r.second;
          K -= (R[x] + 1 + X - 1) / X;
          R[x] -= (R[x] + 1 + X - 1) / X * X;
          M.push_back({R[x], x});
        }
      } else if (P.empty() ||
                 (P.size() && M.size() && abs(P[0].first) >= abs(M[0].first))) {
        auto r = M[0];
        if (r.first < K * X) {
          M.erase(M.begin());
          x = r.second;
          K -= (-R[x] - 1 + X - 1) / X;
          R[x] += (-R[x] - 1 + X - 1) / X * X;
          P.push_back({R[x], x});
        }
      }
    }
    priority_queue<pair<signed long long, int>> Q;
    for (i = 0; i < (N); i++) Q.push({-abs(R[i]), i});
    while (K--) {
      auto r = Q.top();
      Q.pop();
      if (M.size() % 2 == 0) {
        if (R[r.second] >= 0)
          R[r.second] -= X;
        else
          R[r.second] += X;
      } else {
        if (R[r.second] >= 0)
          R[r.second] += X;
        else
          R[r.second] -= X;
      }
      Q.push({-abs(R[r.second]), r.second});
    }
  }
  for (i = 0; i < (N); i++) {
    cout << R[i];
    if (i < N - 1) cout << " ";
  }
  cout << endl;
}
int main(int argc, char** argv) {
  string s;
  int i;
  if (argc == 1) ios::sync_with_stdio(false), cin.tie(0);
  for (i = 0; i < (argc - 1); i++) s += argv[i + 1], s += '\n';
  for (i = 0; i < (s.size()); i++) ungetc(s[s.size() - 1 - i], stdin);
  solve();
  return 0;
}
