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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.PrintStream;
import java.util.PriorityQueue;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.util.Comparator;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Wolfgang Beyer
 */
public class Main {
    public static void main(String[] args) {
        InputStream 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 {
        PriorityQueue minHeap;
        long n;
        long k;
        long x;
        long[] a;

        public void solve(int testNumber, InputReader in, PrintWriter out) {
            n = in.nextLong();
            k = in.nextLong();
            x = in.nextLong();
            a = in.readLongArray((int) n);
            minHeap = new PriorityQueue((int) n, new MyComparator());

            boolean negProd = false;
            int zeros = 0;
            for (int i = 0; i < n; i++) {
                minHeap.add(new element(a[i], i));
                if (a[i] < 0) negProd = !negProd;
                if (a[i] == 0) zeros++;
            }

            while ((zeros > 0) && (k > 0)) {
                element first = (element) minHeap.poll();
                if (!negProd) {
                    first.value = -x;
                    negProd = true;
                } else {
                    first.value = x;
                }
                a[first.index] = first.value;
                k--;
                zeros--;
                minHeap.add(first);
            }

            if ((k > 0) && (negProd)) solveNegProd();
            else if (x * k > Math.abs(((element) minHeap.peek()).value)) {
                element first = (element) minHeap.poll();
                long y = first.value / x;
                if (first.value > 0) y++;
                else y--;
                first.value = first.value - y * x;
                a[first.index] = first.value;
                minHeap.add(first);
                k = k - Math.abs(y);
                solveNegProd();
            } else {
                solvePosProd();
            }

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

        }

        public void solveNegProd() {
            //System.out.println("solve neg");
            //for (int i = 0; i < n; i++) System.out.print(a[i] + " ");
            //System.out.println();

            for (long i = k; i > 0; i--) {
                element first = (element) minHeap.poll();
                //System.out.println("changing " + first.value);
                if (first.value > 0) {
                    first.value += x;
                    a[first.index] += x;
                } else {
                    first.value -= x;
                    a[first.index] -= x;
                }
                minHeap.add(first);
            }
        }

        public void solvePosProd() {
            element first = (element) minHeap.poll();
            if (first.value > 0) {
                first.value -= x * k;
                a[first.index] -= x * k;
            } else {
                first.value += x * k;
                a[first.index] += x * k;
            }
            minHeap.add(first);
        }

        class MyComparator implements Comparator<element> {
            public int compare(element x, element y) {
                //return (int) Math.abs(x.value) - (int) Math.abs(y.value);
                long res = Math.abs(x.value) - Math.abs(y.value);
                if (res > 0) return 1;
                else if (res == 0) return 0;
                return -1;
            }

        }

        class element {
            long value;
            int index;

            public element(long x, int i) {
                //isPos = (x > 0);
                //value = Math.abs(x);
                value = x;
                index = i;
            }

        }

    }

    static class InputReader {
        private static BufferedReader in;
        private static StringTokenizer tok;

        public InputReader(InputStream in) {
            this.in = new BufferedReader(new InputStreamReader(in));
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public long[] readLongArray(int n) {
            long[] ar = new long[n];
            for (int i = 0; i < n; i++) {
                ar[i] = nextLong();
            }
            return ar;
        }

        public String next() {
            try {
                while (tok == null || !tok.hasMoreTokens()) {
                    tok = new StringTokenizer(in.readLine());
                }
            } catch (IOException ex) {
                System.err.println("An IOException was caught :" + ex.getMessage());
            }
            return tok.nextToken();
        }

    }
}

