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.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.PrintStream;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

/*
 public class _791D {

 }

 */

public class _721D {
  class ele {
    long num;
    int ind;

    /**
     * @param num
     * @param ind
     */
    public ele(long num, int ind) {
      super();
      this.num = num;
      this.ind = ind;
    }
  }

  public void solve() throws FileNotFoundException {
    InputStream inputStream = System.in;

    InputHelper inputHelper = new InputHelper(inputStream);

    PrintStream out = System.out;

    // actual solution
    int n = inputHelper.readInteger();
    int k = inputHelper.readInteger();

    int x = inputHelper.readInteger();

    long[] a = new long[n];

    int maxneg = -1;
    int minpos = -1;
    int neg = 0;
    int pos = 0;
    int zero = 0;

    for (int i = 0; i < n; i++) {
      a[i] = inputHelper.readInteger();
      if (a[i] < 0) {
        neg++;
      } else if (a[i] == 0) {
        zero++;
      } else {
        pos++;
      }

      if (a[i] > 0 && (minpos == -1 || a[i] < a[minpos])) {
        minpos = i;
      }

      if (a[i] < 0 && (maxneg == -1 || a[i] > a[maxneg])) {
        maxneg = i;
      }
    }

    int rem = k;
    boolean expand = true;

    if (zero == n) {
      if (k < n) {
        for (int i = 0; i < n; i++) {
          System.out.print(a[i] + " ");
        }
        return;
      }
      a[0] -= x;

      for (int i = 1; i < n; i++) {
        a[i] += x;
      }

      rem -= n;
    } else {
      if (k < zero) {
        for (int i = 0; i < n; i++) {
          System.out.print(a[i] + " ");
        }
        return;
      } else {
        if ((zero + neg) % 2 == 1) {
          for (int i = 0; i < n; i++) {
            if (a[i] == 0) {
              a[i] -= x;
              rem--;
            }
          }
        } else {
          if (zero > 0) {
            for (int i = 0; i < n; i++) {
              if (a[i] == 0) {
                a[i] += x;
                rem--;
                break;
              }
            }
            for (int i = 0; i < n; i++) {
              if (a[i] == 0) {
                a[i] -= x;
                rem--;
              }
            }
          } else {
            int crem = k;

            if (minpos != -1 && (maxneg == -1 || a[minpos] <= -a[maxneg])
                && (a[minpos] + x) / x <= crem) {
              while (a[minpos] >= 0) {
                a[minpos] -= x;
                crem--;
              }
            } else if (maxneg != -1 && (-a[maxneg] + x) / x <= crem) {
              while (a[maxneg] <= 0) {
                a[maxneg] += x;
                crem--;
              }
            } else if (minpos != -1 && (maxneg == -1 || a[minpos] <= -a[maxneg]) && zero == 0
                && (a[minpos] - 1 + x) / x <= crem) {
              while (a[minpos] > 0) {
                a[minpos] -= x;
                crem--;
              }
            } else if (maxneg != -1 && zero == 0 && (-a[maxneg] - 1 + x) / x <= crem) {
              while (a[maxneg] < 0) {
                a[maxneg] += x;
                crem--;
              }
            } else {
              expand = false;
            }

            rem = crem;
          }
        }
      }
    }

    PriorityQueue<ele> pq =
        new PriorityQueue<_721D.ele>((e1, e2) -> (int) Math.signum((Math.abs(e1.num) - Math
            .abs(e2.num))));

    for (int i = 0; i < n; i++) {
      pq.add(new ele(a[i], i));
    }

    while (rem > 0) {
      ele ele = pq.poll();

      if (ele.num < 0) {
        if (expand) {
          ele.num = ele.num - x;
        } else {
          ele.num = ele.num + x;
        }
      } else if (ele.num > 0) {
        if (expand) {
          ele.num = ele.num + x;
        } else {
          ele.num = ele.num - x;
        }
      }

      a[ele.ind] = ele.num;
      pq.add(ele);
      rem--;
    }

    for (int i = 0; i < n; i++) {
      System.out.print(a[i] + " ");
    }
    // end here
  }

  public static void main(String[] args) throws FileNotFoundException {
    (new _721D()).solve();
  }

  class InputHelper {
    StringTokenizer tokenizer = null;
    private BufferedReader bufferedReader;

    public InputHelper(InputStream inputStream) {
      InputStreamReader inputStreamReader = new InputStreamReader(inputStream);
      bufferedReader = new BufferedReader(inputStreamReader, 16384);
    }

    public String read() {
      while (tokenizer == null || !tokenizer.hasMoreTokens()) {
        try {
          String line = bufferedReader.readLine();
          if (line == null) {
            return null;
          }
          tokenizer = new StringTokenizer(line);
        } catch (IOException e) {
          e.printStackTrace();
        }
      }

      return tokenizer.nextToken();
    }

    public Integer readInteger() {
      return Integer.parseInt(read());
    }

    public Long readLong() {
      return Long.parseLong(read());
    }
  }
}
