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 = 200010;
int n, m;
long long x, w;
long long s[maxn];
priority_queue<pair<long long, int>> u;
priority_queue<pair<long long, int>, vector<pair<long long, int>>,
               greater<pair<long long, int>>>
    v;
int main() {
  while (scanf("%d%d%I64d", &n, &m, &x) != EOF) {
    for (int i = 0; i < (n); ++i) {
      scanf("%I64d", &w);
      if (w < 0) {
        u.push({w, i});
      } else {
        v.push({w, i});
      }
    }
    int ne = ((int)(u).size());
    if (ne & 1) {
      for (int i = 0; i < (m); ++i) {
        if (v.empty()) {
          pair<long long, int> p = u.top();
          u.pop();
          u.push({p.first - x, p.second});
        } else {
          pair<long long, int> p = u.top(), q = v.top();
          if (-p.first < q.first) {
            u.pop();
            u.push({p.first - x, p.second});
          } else {
            v.pop();
            v.push({q.first + x, q.second});
          }
        }
      }
    } else {
      int t = m;
      if (ne == 0) {
        pair<long long, int> p = v.top();
        v.pop();
        if (p.first - m * x >= 0) {
          v.push({p.first - m * x, p.second});
        } else {
          t = (p.first + x - 1) / x;
          u.push({p.first - t * x, p.second});
        }
      } else if (ne == n) {
        pair<long long, int> p = u.top();
        u.pop();
        if (p.first + m * x < 0) {
          u.push({p.first + m * x, p.second});
        } else {
          t = (-p.first + x - 1) / x;
          v.push({p.first + t * x, p.second});
        }
      } else {
        pair<long long, int> p = u.top(), q = v.top();
        if (-p.first < q.first) {
          u.pop();
          if (p.first + m * x < 0) {
            u.push({p.first + m * x, p.second});
          } else {
            t = (-p.first + x - 1) / x;
            v.push({p.first + t * x, p.second});
          }
        } else {
          v.pop();
          if (q.first - m * x >= 0) {
            v.push({q.first - m * x, q.second});
          } else {
            t = (q.first + x - 1) / x;
            u.push({q.first - t * x, q.second});
          }
        }
      }
      for (int i = t; i < m; ++i) {
        if (v.empty()) {
          pair<long long, int> p = u.top();
          u.pop();
          u.push({p.first - x, p.second});
        } else if (u.empty()) {
          pair<long long, int> p = v.top();
          v.pop();
          v.push({p.first + x, p.second});
        } else {
          pair<long long, int> p = u.top(), q = v.top();
          if (-p.first < q.first) {
            u.pop();
            u.push({p.first - x, p.second});
          } else {
            v.pop();
            v.push({q.first + x, q.second});
          }
        }
      }
    }
    while (!u.empty()) {
      pair<long long, int> p = u.top();
      s[p.second] = p.first;
      u.pop();
    }
    while (!v.empty()) {
      pair<long long, int> p = v.top();
      s[p.second] = p.first;
      v.pop();
    }
    for (int i = 0; i < (n); ++i) {
      printf("%I64d ", s[i]);
    }
  }
  return 0;
}
