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 
//package codeforces;

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;

/**
 * Created by nitin.s on 06/10/16.
 */
public class MaximAndArray {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int K = in.nextInt();
        int x = in.nextInt();
        long[] a = new long[n];
        for(int i = 0; i < n; ++i) {
            a[i] = in.nextLong();
        }
        int prod = 1;
        int sg = 1;
        for(long v : a) {
            if(v < 0) {
                prod = -prod;
                sg = -sg;
            } else if(v == 0) {
                prod = 0;
            }
        }
        if(prod > 0) {
            int arg = 0;
            for(int i = 0; i < n; ++i) {
                if(Math.abs(a[i]) < Math.abs(a[arg])) {
                    arg = i;
                }
            }
            int first = Long.signum(a[arg]);
            while(K > 0 && Long.signum(a[arg]) == first) {
                if(first > 0) {
                    a[arg] -= x;
                } else {
                    a[arg] += x;
                }
                K--;
            }
            prod = 1;
            sg = 1;
            for(long v : a) {
                if(v < 0) {
                    prod = -prod;
                    sg = -sg;
                } else if(v == 0) {
                    prod = 0;
                }
            }
        }
        PriorityQueue<Long[]> pq = new PriorityQueue<Long[]>(10000, new Comparator<Long[]>() {
            @Override
            public int compare(Long[] u, Long[] v) {
                return Long.compare(Math.abs(u[0]), Math.abs(v[0]));
            }
        });
        for(int i = 0; i < n; ++i) {
            pq.add(new Long[] {a[i], (long)i});
        }
        for(int i = 0; i < K; ++i) {
            Long[] cur = pq.poll();
            if(cur[0] > 0) {
                cur[0] += x;
            } else if(cur[0] < 0) {
                cur[0] -= x;
            } else if(sg == 1) {
                cur[0] -= x;
                sg = -sg;
            } else {
                cur[0] += x;
            }
            pq.add(cur);
        }
        for (Long[] cur : pq) {
            a[cur[1].intValue()] = cur[0];
        }
        for(int i = 0; i < n; ++i) {
            System.out.print(a[i] + " ");
        }
        System.out.println();
    }
}
