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.*;

public class D {

    private static final boolean TEST_CASES = false;

    private static class Solver {
	void solve(int testCaseNo) {
		int n = IO.nextInt(), k = IO.nextInt(), x = IO.nextInt();
		int[] arr = new int[n];
		for (int i = 0; i < n; ++i) {
			arr[i] = IO.nextInt();
		}

		if (n == 1) {
			long r = arr[0];
			r -= (long)x * k;
			IO.writer.println(r);
			return;
		}

		final int Gp = 1000000001, Gn = -1000000001;

		int mp = Gp, ip = -1;
		for (int i = 0; i < n; ++i) {
			if (arr[i] >= 0) {
				if (arr[i] < mp) {
					mp = arr[i];
					ip = i;
				}
			}
		}
		int mn = Gn, in = -1;
		for (int i = 0; i < n; ++i) {
			if (arr[i] < 0) {
				if (arr[i] > mn) {
					mn = arr[i];
					in = i;
				}
			}
		}
		int fg = 1;
		for (int i = 0; i < n; ++i) {
			if (arr[i] < 0) fg *= -1;
		}

		if (fg > 0) {
			if (mp <= Math.abs(mn)) {
				int op = mp / x;
				op++;
				op = Math.min(op, k);
				k -= op;
				arr[ip] -= op * x;
			} else {
				int op = Math.abs(mn / x);
				op++;
				op = Math.min(op, k);
				k -= op;
				arr[in] += op * x;
			}
		}


		Num[] nums = new Num[n];
		for (int i = 0; i < n; ++i) {
			nums[i] = new Num(Math.abs(arr[i]), (arr[i] < 0) ? true : false, i);
		}

		doOps(nums, k, x);
		for (int i = 0; i < n; ++i) {
			long vv = nums[i].val;
			if (nums[i].isNeg) vv *= -1;
			if (i > 0) IO.writer.print(" ");
			IO.writer.print(vv);
		}
		IO.writer.println();

	}
	void doOps(Num[] nums, int k, int x) {
		int n = nums.length;
		PriorityQueue<Num> pq = new PriorityQueue<>();
		for (int i = 0; i < n; ++i) {
			pq.add(nums[i]);
		}

		while (k > 0) {
			Num num = pq.poll();
			Num hd = pq.peek();
			long n1 = num.val;
			long n2 = hd.val;
			long op = (n2 - n1) / x;
			op++;
			op = Math.min(op, k);
			k -= op;
			num.val = n1 + op*x;
			pq.add(num);
		}
	}
	static class Num implements Comparable<Num> {
		long val;
		boolean isNeg;
		int id;
		Num(long vv, boolean isN, int ii) {
			val = vv;
			isNeg = isN;
			id = ii;
		}
		public int compareTo(Num o) {
			return Long.compare(val, o.val);
		}
	}

	
    }

    private static class IO {

	private static final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
	static final PrintWriter writer = new PrintWriter(System.out);

	private static StringTokenizer tokenizer = null;

	static String nextToken() {
	    checkTokenizer();
	    return tokenizer.nextToken();
	}

	static long nextLong() {
		return Long.parseLong(nextToken());
	}
	static int nextInt() {
	    return Integer.parseInt(nextToken());
	}

	static void close() {
	    writer.flush();
	}

	private static boolean isTokenizerEmpty() {
	    return tokenizer == null || !tokenizer.hasMoreTokens();
	}

	private static void checkTokenizer() {
	    while (isTokenizerEmpty()) {
		try {
		    tokenizer = new StringTokenizer(reader.readLine());
		} catch (IOException e) {
		    throw new RuntimeException(e);
		}
	    }
	}
    }

    private static void go() {
	int testCases = TEST_CASES ? IO.nextInt() : 1;

	Solver solver = new Solver();
	for (int testCase = 0; testCase < testCases; testCase++) {
	    solver.solve(testCase);
	}
    }

    public static void main(String[] args) {
	try {
	    go();
	} finally {
	    IO.close();
	}
    }
}
