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.IOException;
import java.io.InputStreamReader;
import java.io.Reader;
import java.util.PriorityQueue;
import java.util.Random;
import java.util.StringTokenizer;

public class D {
    public static void main(String[] args) {
//        Scanner sc = new Scanner(System.in);
        FastScanner sc = new FastScanner();

        int n = sc.nextInt();
        int opLimit = sc.nextInt();
        long x = sc.nextLong();

        /**
         *  Case: even # of negatives:
         *      1a: if we can flip the sign of the non-zero number with the smallest abs. value:
         *          do it,
         *          and then greedily increase (abs. value) of numbers, BEWARE OF ZEROS
         *      1b: else if we can make some number zero:
         *          do it,
         *          and then stop
         *      1c: else:
         *          greedily make larger numbers smaller
         *
         *   Case: odd # of negatives:
         *      Greedily increase abs. value of numbers, BEWARE OF ZEROS
         */

        int negativeCount = 0;
        int zeroCount = 0;
        long smallestNonZeroAbs = Integer.MAX_VALUE;
        Num smallestNonZeroAbsNum = null;
        Num[] nums = new Num[n];
        for (int i = 0; i < n; i++) {
            long a = sc.nextLong();
            Num num = new Num(a);
            nums[i] = num;
            long abs = Math.abs(a);
            if (abs < smallestNonZeroAbs && abs != 0) {
                smallestNonZeroAbs = abs;
                smallestNonZeroAbsNum = num;
            }
            if (a < 0) {
                negativeCount++;
            } else if (a == 0) {
                zeroCount++;
            }
        }

        int numOpsUsed = 0;

        int zeroKillerIdx = 0;
        while (numOpsUsed < opLimit && /*numOpsUsed < zeroCount && */zeroKillerIdx < n) {
            if (nums[zeroKillerIdx].val == 0) {
                if (negativeCount % 2 == 0) {
                    nums[zeroKillerIdx].val -= x;
                    negativeCount++;
                } else {
                    nums[zeroKillerIdx].val += x;
                }
                numOpsUsed++;
            }
            zeroKillerIdx++;
        }

        if (numOpsUsed < opLimit) {
            if (smallestNonZeroAbsNum == null) {
                // At this point, there are no zeros
                throw new Error();
            }

            boolean increaseNumbers = true;

            if (negativeCount % 2 == 0) {
                int numOpsNeeded = (int) Math.floorDiv(smallestNonZeroAbs, x) + 1;
                if (numOpsUsed + numOpsNeeded <= opLimit) {
                    // 1a (and 1b)
                    numOpsUsed += numOpsNeeded;
                    if (smallestNonZeroAbsNum.val < 0) {
                        smallestNonZeroAbsNum.val += numOpsNeeded * x;
                        negativeCount--;
                    } else {
                        smallestNonZeroAbsNum.val -= numOpsNeeded * x;
                        negativeCount++;
                    }

                    // Now greedily increase numbers
                    increaseNumbers = true;
                } else {
                    // 1c
                    increaseNumbers = false;
                    int numUsableOps = opLimit - numOpsUsed;
                    if (smallestNonZeroAbsNum.val < 0) {
                        smallestNonZeroAbsNum.val += numUsableOps * x;
                    } else {
                        smallestNonZeroAbsNum.val -= numUsableOps * x;
                    }
                    numOpsUsed += numUsableOps;
                }
            }

            if (increaseNumbers) {
                PriorityQueue<Num> pq = new PriorityQueue<>();
                for (Num num : nums) {
                    pq.offer(num);
                }
                while (numOpsUsed < opLimit) {
                    Num num = pq.poll();
                    if (num.val > 0) {
                        num.val += x;
                    } else {
                        num.val -= x;
                    }
                    pq.offer(num);
                    numOpsUsed++;
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            if (i > 0) sb.append(' ');
            sb.append(nums[i].val);
        }
        System.out.println(sb);
    }

    static class Num implements Comparable<Num> {
        long val;

        public Num(long val) {
            this.val = val;
        }

        @Override
        public int compareTo(Num o) {
            return Long.compare(Math.abs(val), Math.abs(o.val));
        }

        @Override
        public String toString() {
            return Long.toString(val);
        }
    }

    static void shuffle(int[] arr) {
        Random rng = new Random();
        int length = arr.length;
        for (int idx = 0; idx < arr.length; idx++) {
            int toSwap = idx + rng.nextInt(length-idx);
            int tmp = arr[idx];
            arr[idx] = arr[toSwap];
            arr[toSwap] = tmp;
        }
    }

    public static class FastScanner {
        BufferedReader br;
        StringTokenizer st;
        public FastScanner(Reader in) {
            br = new BufferedReader(in);
        }
        public FastScanner() {
            this(new InputStreamReader(System.in));
        }
        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        int nextInt() {
            return Integer.parseInt(next());
        }
        long nextLong() {
            return Long.parseLong(next());
        }
        double nextDouble() {
            return Double.parseDouble(next());
        }
        String readNextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
        int[] readIntArray(int n) {
            int[] a = new int[n];
            for (int idx = 0; idx < n; idx++) {
                a[idx] = nextInt();
            }
            return a;
        }
        long[] readLongArray(int n) {
            long[] a = new long[n];
            for (int idx = 0; idx < n; idx++) {
                a[idx] = nextLong();
            }
            return a;
        }
    }
}
