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.*;
import java.util.*;
import java.util.concurrent.ThreadLocalRandom;
public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		InputReader in = new InputReader(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		Solve solver = new Solve();
		solver.solve(1, in, out);
		out.close();
	}

}

class Solve {
	
	public void solve(int cas, InputReader in, PrintWriter out) {
		int n = in.nextInt(), k = in.nextInt(), x = in.nextInt();
		final int inf = 0x3f3f3f3f;
		int[] a = new int[n];
		int p = 0, cnt = 0;
		for(int i = 0; i < n; ++i) {
			a[i] = in.nextInt();
			if(Math.abs(a[p]) > Math.abs(a[i])) p = i;
			if(a[i] < 0) ++cnt;
		}
		if(cnt % 2 == 0 && Math.abs(a[p]) < (long)k * x) {
			if(a[p] < 0) {
				int temp = a[p] % x;
				if(temp <= 0) temp += x;
				k -= (temp - a[p]) / x;
				a[p] = temp;
			} else {
				int temp = a[p] % x;
				if(temp >= 0) temp -= x;
				k -= (a[p] - temp) / x;
				a[p] = temp;
			}
			++cnt;
		}
		else if(cnt % 2 == 0 && Math.abs(a[p]) == (long)k * x) {
			a[p] = 0;
			k = 0; x = 0;
		}

		else if(cnt % 2 == 0) {
			if(a[p] < 0) {
				a[p] += x * k;
			} else {
				a[p] -= x * k;
			}
			x = k = 0;
		}
		Long l = 0l, r = (long)inf * x;
		if(cnt % 2 == 1) {
			while(l < r) {
				long m = l + r + 1 >> 1;
				long tot = 0;
				for(int i = 0; i < n; ++i) if(m > Math.abs(a[i])){
					tot += (m - Math.abs(a[i])) / x;
				}
				if(tot > k) r = m-1;
				else l = m;
			}
		}
		cnt = 0;
		for(int i = 0; i < n; ++i) {
			if(l > Math.abs(a[i])) cnt += (l - Math.abs(a[i])) / x;
		}
		cnt = k - cnt;
		for(int i = 0; i < n; ++i) {
			if(a[i] < 0) out.print('-');
			if(cnt > 0 && l+1 > Math.abs(a[i]) && (l+1-Math.abs(a[i])) % x == 0) {
				--cnt;
				out.print(l+1 + " ");
			}
			else if(l > Math.abs(a[i])) out.print((l - Math.abs(a[i])) / x * x + Math.abs(a[i]) + " ");
			else out.print(Math.abs(a[i]) + " ");
		}
	}
}

class InputReader {
	public BufferedReader reader;
	public StringTokenizer tokenizer;
	
	public InputReader(InputStream stream) {
		reader = new BufferedReader(new InputStreamReader(stream), 32768);
		tokenizer = null;
	}
	
	public String next() {
		while (tokenizer == null || !tokenizer.hasMoreTokens()) {
			try {
				tokenizer = new StringTokenizer(reader.readLine());
			} catch (IOException e) {
				throw new RuntimeException(e);
			}
		}
		return tokenizer.nextToken();
	}
	
	public int nextInt() {
		return Integer.parseInt(next());
	}
	
	public Long nextLong() {
		return Long.parseLong(next());
	}
}