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


 */
public class d 
{
	public static void main(String[] arg) throws IOException
	{
		new d();
	}
	
	public d() throws IOException
	{
		FastScanner in = new FastScanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		int n = in.nextInt();
		int k = in.nextInt();
		long x = in.nextInt();
		long[] val = new long[n];
		for(int i = 0; i < n; i++) val[i] = in.nextInt();
		// Check if it is already negative
		int containZero = 0;
		boolean flag = false;
		for(int i = 0; i < n; i++)
		{
			if(val[i] < 0) flag = !flag;
			if(val[i] == 0) containZero++;
		}
		if(containZero > 0)
		{

			if(k >= containZero)
			{
				for(int i = 0; i < n; i++)
				{
					if(val[i] == 0)
					{
						if(flag)
						{
							val[i] += x;
							k--;
						}
						else
						{
							flag = !flag;
							val[i] -= x;
							k--;
						}
					}
				}
				maximize(val, k, x);
			}
		}
		else if(flag)
		{
			maximize(val, k, x);
		}
		else
		{
			// Check if I can turn it negative
			int idx = -1;
			for(int i = 0; i < n; i++)
			{
				if(val[i] >= 0 && val[i]-k*x < 0)
				{
					if(idx == -1) idx = i;
					else
					{
						if(Math.abs(val[i]) < Math.abs(val[idx])) idx = i;
					}
				}
				if(val[i] < 0 && val[i]+k*x > 0)
				{
					if(idx == -1) idx = i;
					else
					{
						if(Math.abs(val[i]) < Math.abs(val[idx])) idx = i;
					}
				}
			}
			//out.println(idx);
			if(idx != -1)
			{
				if(val[idx] < 0)
				{
					int amt = (int)(Math.abs(val[idx])/x+1);
					val[idx] += amt*x;
					maximize(val, k-amt, x);
				}
				else
				{
					int amt = (int)(val[idx]/x+1);
					val[idx] -= amt*x;
					maximize(val, k-amt, x);
				}
			}
			else
			{
				// Check if I can put a zero
				flag = false;
				for(int i = 0; i < n; i++)
				{
					if(val[i] > 0 && val[i]-k*x == 0)
					{
						flag = true;
						val[i] = 0;
						break;
					}
					if(val[i] < 0 && val[i]+k*x == 0)
					{
						flag = true;
						val[i] = 0;
						break;
					}
					if(val[i] == 0)
					{
						flag = true; 
						break;
					}
				}
				if(!flag)
				{
					// If not any of this then we need to minimize
					minimize(val, k, x);
				}
				
			}
		}
		for(long v : val) out.print(v + " ");
		out.println();
		in.close(); out.close();
	}
	void maximize(long[] val, int k, long x)
	{
		PriorityQueue<Pair> pq = new PriorityQueue<Pair>();
		for(int i = 0; i < val.length; i++) pq.add(new Pair(val[i], i));
		for(int i = 0; i < k; i++)
		{
			Pair p = pq.poll();
			if(p.v < 0) val[p.idx] -= x;
			else val[p.idx] += x;
			pq.add(new Pair(val[p.idx], p.idx));
		}

	}
	void minimize(long[] val, int k, long x)
	{
		int idx = 0;
		for(int i = 1; i < val.length; i++)
		{
			if(val[i] < val[idx]) idx = i;
		}
		val[idx] -= k*x;
	}
	class Pair implements Comparable<Pair>
	{
		long v;
		int idx;
		public Pair(long a, int b)
		{
			v = a;
			idx = b;
		}
		public int compareTo(Pair p)
		{
			return Long.compare(Math.abs(v), Math.abs(p.v));
		}
	}
	int oo = 1_000_000;
	char[] fuse(char[] p, char[] s)
	{
		char[] ret = new char[p.length+s.length+1];
		for(int i = 0; i < p.length; i++) ret[i] = p[i];
		ret[p.length] = '$';
		for(int i = 0; i < s.length; i++) ret[i+p.length+1] = s[i];
		return ret;
	}

	class ZValue 
	{
		int[] z;
		public ZValue(char[] s)
		{
			int n = s.length;
			z = new int[n];
			int L = 0, R = 0;
			for (int i = 1; i < n; i++) {
			  if (i > R) {
			    L = R = i;
			    while (R < n && s[R-L] == s[R]) R++;
			    z[i] = R-L; R--;
			  } else {
			    int k = i-L;
			    if (z[k] < R-i+1) z[i] = z[k];
			    else {
			      L = i;
			      while (R < n && s[R-L] == s[R]) R++;
			      z[i] = R-L; R--;
			    }
			  }
			}
		}
	}
	class AhoCorasick 
	{
		public final int ALPHA = 26;
		public int nodeCount;
		public int[][] transition;
		public boolean[] term;
		public AhoCorasick(String[] strs)
		{
			int maxNodes = 1;
			for(String s : strs) maxNodes += s.length();
			int[][] children = new int[ALPHA][maxNodes];
			boolean[] leaf = new boolean[maxNodes];
			nodeCount = 1;
			for(String s : strs)
			{
				int node = 0;
				for(char ch : s.toCharArray())
				{
					int c = ch - 'a';
					if(children[c][node] == 0)
					{
						children[c][node] = nodeCount;
						nodeCount++;
					}
					node = children[c][node];
				}
				leaf[node] = true;
			}
			transition = new int[ALPHA][nodeCount];
			term = new boolean[nodeCount];
			ArrayDeque<Integer> queue = new ArrayDeque<Integer>();
			queue.add(0); queue.add(0);
			while(queue.size() > 0)
			{
				int node = queue.remove();
				int suffLink = queue.remove();
				term[node] = leaf[node] || term[suffLink];
				for(int ch = 0; ch < ALPHA; ch++)
				{
					if(children[ch][node] != 0)
					{
						transition[ch][node] = children[ch][node];
						queue.add(children[ch][node]);
						queue.add(node == 0 ? 0 : transition[ch][suffLink]);
					}
					else
					{
						transition[ch][node] = transition[ch][suffLink];
					}
				}
			}
		}
	}
	class FastScanner
	{
		BufferedReader br;
		StringTokenizer st;
		public FastScanner(InputStream in)
		{
			br = new BufferedReader(new InputStreamReader(in));
			st = new StringTokenizer("");
		}
		public String next() throws IOException
		{
			while(!st.hasMoreTokens()) st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}
		public int nextInt() throws IOException
		{
			return Integer.parseInt(next());
		}
		public long nextLong() throws IOException
		{
			return Long.parseLong(next());
		}
		public void close() throws IOException
		{
			br.close();
		}
	}
}