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 
import java.io.*;
import java.util.*;

public class Main {

  int signum(long x) {
    return x > 0 ? 1 : (x == 0 ? 0 : -1);
  }

  int diff(int a, int x) {
    return Math.abs(Math.abs(a) - x);
  }

  static class Entry implements Comparable<Entry> {
    long val;
    int idx;
    Entry(long _val, int _idx) { 
      val = _val; idx = _idx;
    }

    public int compareTo(Entry o) {
      if (val != o.val) return val < o.val ? -1 : 1;
      return idx - o.idx;
    }
  }
    
  public void solve() throws IOException {
    int n = nextInt(), k = nextInt(), x = nextInt();
    long a[] = new long[n];
    int negCnt = 0;
    for (int i = 0 ; i < n ; i ++) {
      a[i] = nextInt();
      if (a[i] < 0) negCnt ++;
    }
    if (negCnt % 2 == 0) {
      int idxMinAbs = -1;
      for (int i = 0 ; i < n ; i++) {
        if ( idxMinAbs == -1 || Math.abs(a[i]) < Math.abs(a[idxMinAbs]) ) {
          idxMinAbs = i;
        }
      }
      int finalSign = signum(a[idxMinAbs]) >= 0 ? -1 : 1;
      while (k > 0 && signum(a[idxMinAbs]) != finalSign) {
         a[idxMinAbs] += x * finalSign;
         k--;
      }// TODO: case when changing minabs value lead to "over increased" product
    }
    if (k == 0) {
      for (int i = 0 ; i < n ; i ++) out.print(a[i] + " " );
      out.println();
      return;
    }
    if (k > 0) {
      PriorityQueue<Entry> q = new PriorityQueue<>();
      long s[] = new long[n];
      //System.err.println(Arrays.toString(a));
      for (int i = 0 ; i < n ; i ++) {
        s[i] = signum(a[i]);
        q.add(new Entry(Math.abs(a[i]), i));
      }
      while (k > 0) {
        k--;
        Entry top = q.poll();
        //System.err.println(top.val);
        q.add(new Entry(top.val + x, top.idx));
      }

      while (!q.isEmpty()) {
        Entry top = q.poll();
        if (s[top.idx] < 0) s[top.idx] = -top.val;
        else s[top.idx] = top.val;
      }

      for (int i = 0 ; i < n ; i ++) out.print(s[i] + " ");
      out.println();
    }
    
  }

    

    
    
  BufferedReader bf;
  StringTokenizer st;
  PrintWriter out;
  
  public String next() throws IOException {
    while (st == null || !st.hasMoreTokens()) 
        st = new StringTokenizer(bf.readLine());
    return st.nextToken();
  }
  public int nextInt() throws IOException {
    return Integer.parseInt(next());
  }
  
  public long nextLong() throws IOException {
      return Long.parseLong(next());
  }

  public Main() throws IOException {
    bf = new BufferedReader(new InputStreamReader(System.in));
    out = new PrintWriter(new OutputStreamWriter(System.out));		
    solve();
    bf.close();
    out.close();
  }
  
  public static void main(String args[]) throws IOException {
      new Main();
  }
}