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.PrintWriter;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class CF721D {
    public static void main(String[] args) throws IOException {
        FastScanner sc = new FastScanner();
        PrintWriter pw = new PrintWriter(System.out);
        int n = sc.nextInt(), k = sc.nextInt(), x = sc.nextInt();
        long[] a = new long[n];
        for (int i = 0; i < n; i++)
            a[i] = sc.nextInt();

        solve(a, k, x);
        for (int i = 0; i < n; i++)
            pw.print(a[i] + " ");

        pw.println();
        sc.close();
        pw.close();
    }

    public static void solve(long[] a, int k, int x) {
        PriorityQueue<Integer> q = new PriorityQueue<Integer>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                long diff = Math.abs(a[o1]) - Math.abs(a[o2]);
                return diff > 0 ? 1 : diff < 0 ? -1 : 0;
            }
        });

        for (int i = 0; i < a.length; i++)
            q.add(i);

        boolean posProd = true;
        for (int i = 0; i < a.length; i++)
            posProd = !(posProd ^ a[i] >= 0);

        while (k-- > 0) {
            int minIdx = q.remove();
            long min = a[minIdx];
            boolean posMin = min >= 0;
            if (posProd == posMin)
                min -= x;
            else
                min += x;
            a[minIdx] = min;
            q.add(minIdx);
            posProd = posProd ^ !(min >= 0 == posMin);
        }
    }

    static class FastScanner {
        BufferedReader in;
        StringTokenizer st;

        public FastScanner() {
            this.in = new BufferedReader(new InputStreamReader(System.in));
        }

        public String nextToken() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(in.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

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

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

        public double nextDouble() {
            return Double.parseDouble(nextToken());
        }

        public void close() throws IOException {
            in.close();
        }
    }
}