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 
// -*- coding: utf-8 -*-
//import java.awt.*;
import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;

public class Main {
  public static void main(String[] args) {
    InputStream inputStream;
    if (args.length > 0 && args[0].equals("devTesting")) {
      try {
        inputStream = new FileInputStream(args[1]);
      } catch(FileNotFoundException e) {
        throw new RuntimeException(e);
      }
    } else {
      inputStream = System.in;
    }
    OutputStream outputStream = System.out;
    InputReader in = new InputReader(inputStream);
    PrintWriter out = new PrintWriter(outputStream);
    TaskD solver = new TaskD();
    solver.solve(1, in, out);
    out.close();
  }
    
  static class TaskD {    
    long k, x;
    int n;
    long[] a;
      
    class Node {
      long v;
      int mxl, mxr, idx;
      Node lc, rc;
      
      Node(int nmxl, int nmxr) {
        mxl = nmxl;
        mxr = nmxr;
      }
    }
    
    void solve(int testNumber, InputReader in, PrintWriter out) {
      n = in.nextInt();
      k = in.nextInt();
      x = in.nextInt();
      a = new long[n];
      int neg = 0;
      for (int i = 0; i < n; ++i) {
        a[i] = in.nextInt();
        if (a[i] < 0)
          ++neg;
      }
      if (neg % 2 == 0) {
        long min = Long.MAX_VALUE / 2;
        int idx = -1;
        for (int i = 0; i < n; ++i) {
          long abs = Math.abs(a[i]);
          if (abs <= k * x && abs < min) {
            min = abs;
            idx = i;
          }
        }
        if (idx != -1) {
          boolean isNeg = a[idx] < 0;
          k -= Math.abs(a[idx]) / x;
          a[idx] -= a[idx] / x * x;
          if (k > 0) {
            --k;
            if (isNeg) {
              a[idx] += x;
              --neg;
            } else {
              a[idx] -= x;
              ++neg;
            }
          }
        }
      }
      Node root = construct(a, 0, n - 1);
      while (k > 0) {
        int idx = query(root, 0, n - 1);
        if (a[idx] >= 0)
          a[idx] += neg % 2 != 0 ? x : -x;
        else
          a[idx] += neg % 2 != 0 ? -x : x;
        update(root, idx, a[idx]);
        --k;
      }
      for (int i = 0; i < n; ++i) {
        if (i > 0)
          out.print(" ");
        out.print(a[i]);
      }
      out.println();
    }
    
    Node construct(long[] a, int l, int r) {
      Node nd = new Node(l, r);
      if (l == r) {
        nd.v = a[l];
        nd.idx = l;
        return nd;
      }
      int m = (l + r) / 2;
      nd.lc = construct(a, l, m);
      nd.rc = construct(a, m + 1, r);
      if (Math.abs(nd.lc.v) <= Math.abs(nd.rc.v)) {
        nd.v = nd.lc.v;
        nd.idx = nd.lc.idx;
      } else {
        nd.v = nd.rc.v;
        nd.idx = nd.rc.idx;
      }
      return nd;
    }
    
    int query(Node nd, int l, int r) {
      if (l > nd.mxr || r < nd.mxl)
        return Integer.MAX_VALUE / 2;
      if (l <= nd.mxl && r >= nd.mxr)
        return nd.idx;
      int la = query(nd.lc, l, r);
      int ra = query(nd.rc, l, r);
      if (la < Integer.MAX_VALUE / 2 && ra < Integer.MAX_VALUE / 2)
        if (Math.abs(nd.lc.v) <= Math.abs(nd.rc.v))
          return nd.lc.idx;
        else
          return nd.rc.idx;
      if (la < Integer.MAX_VALUE / 2)
        return nd.lc.idx;
      return nd.rc.idx;
    }
    
    void update(Node nd, int i, long v) {
      if (nd.mxl == i && nd.mxl == nd.mxr) {
        nd.v = v;
        nd.idx = i;
        return;
      }
      if (nd.mxr < i && nd.mxl < i || nd.mxr > i && nd.mxl > i)
        return;
      update(nd.lc, i, v);
      update(nd.rc, i, v);
      if (Math.abs(nd.lc.v) <= Math.abs(nd.rc.v)) {
        nd.v = nd.lc.v;
        nd.idx = nd.lc.idx;
      } else {
        nd.v = nd.rc.v;
        nd.idx = nd.rc.idx;
      }      
    }

  }
      
  static class InputReader {
    public BufferedReader reader;
    public StringTokenizer tokenizer;

    public InputReader(InputStream stream) {
      reader = new BufferedReader(new InputStreamReader(stream));
      tokenizer = null;
    }

    public String next() {
      while (tokenizer == null || !tokenizer.hasMoreTokens()) {
        try {
          tokenizer = new StringTokenizer(reader.readLine());
        } catch (IOException e) {
          throw new RuntimeException(e);
        }
      }
      return tokenizer.nextToken();
    }
    
    public String nextLine() {
      try {
        return reader.readLine();
      } catch(IOException e) {
        throw new RuntimeException(e);
      }
    }

    public int nextInt() {
      return Integer.parseInt(next());
    }

    public long nextLong() {
      return Long.parseLong(next());
    }
    
    public double nextDouble() {
      return Double.parseDouble(next());
    }

    public boolean hasInput() {
      try {
        if (tokenizer != null && tokenizer.hasMoreTokens()) {
          return true;
        }
        reader.mark(1);
        int ch = reader.read();
        if (ch != -1) {
          reader.reset();
          return true;
        }
        return false;
      } catch(IOException e) {
        throw new RuntimeException(e);
      }
    }
    
  }
}
