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 
// practice with rainboy
import java.io.*;
import java.util.*;

public class CF721D extends PrintWriter {
	CF721D() { super(System.out, true); }
	Scanner sc = new Scanner(System.in);
	public static void main(String[] $) {
		CF721D o = new CF721D(); o.main(); o.flush();
	}

	long[] aa;
	int[] ss;
	int[] pq, iq;
	int cnt;
	boolean less(int u, int v) {
		return aa[u] < aa[v];
	}
	int i2(int i) {
		return (i *= 2) > cnt ? 0 : i < cnt && less(pq[i + 1], pq[i]) ? i + 1 : i;
	}
	void pq_up(int u) {
		int i, j;
		for (i = iq[u]; (j = i / 2) > 0 && less(u, pq[j]); i = j)
			pq[iq[pq[j]] = i] = pq[j];
		pq[iq[u] = i] = u;
	}
	void pq_dn(int u) {
		int i, j;
		for (i = iq[u]; (j = i2(i)) > 0 && less(pq[j], u); i = j)
			pq[iq[pq[j]] = i] = pq[j];
		pq[iq[u] = i] = u;
	}
	void pq_add(int u) {
		iq[u] = ++cnt;
		pq_up(u);
	}
	void output(int n) {
		for (int i = 0; i < n; i++)
			print(aa[i] * ss[i] + " ");
		println();
	}
	void main() {
		int n = sc.nextInt();
		int k = sc.nextInt();
		int x = sc.nextInt();
		aa = new long[n];
		ss = new int[n];
		int z = 0, s = 1;
		for (int i = 0; i < n; i++) {
			int a = sc.nextInt();
			if (a > 0) {
				aa[i] = a;
				ss[i] = 1;
			} else if (a < 0) {
				aa[i] = -a;
				ss[i] = -1;
				s = -s;
			} else
				z++;
		}
		if (z > k) {
			output(n);
			return;
		}
		if (z > 0) {
			k -= z;
			for (int i = 0; i < n; i++)
				if (ss[i] == 0) {
					aa[i] = x;
					if (--z == 0) {
						ss[i] = -s;
						break;
					}
					ss[i] = 1;
				}
		} else if (s == 1) {
			int i_ = 0;
			for (int i = 1; i < n; i++)
				if (aa[i_] > aa[i])
					i_ = i;
			long k_ = aa[i_] / x + 1;
			if (k <= k_) {
				aa[i_] -= k * x;
				output(n);
				return;
			}
			aa[i_] = k_ * x - aa[i_];
			ss[i_] = -ss[i_];
			k -= k_;
		}
		pq = new int[1 + n];
		iq = new int[n];
		for (int i = 0; i < n; i++)
			pq_add(i);
		while (k-- > 0) {
			int i = pq[1];
			aa[i] += x;
			pq_dn(i);
		}
		output(n);
	}
}
