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 Main {
	public static void main(String args[]) {new Main().run();}

	FastReader in = new FastReader();
	PrintWriter out = new PrintWriter(System.out);
	void run(){
		work();
		out.flush();
	}
	long mod=1000000007;
	void work() {
		int n=in.nextInt(),k=in.nextInt(),x=in.nextInt();
		long[] A=new long[n];
		int f=1;
		int index=-1;
		long a=Long.MAX_VALUE;
		for(int i=0;i<n;i++) {
			A[i]=in.nextLong();
			if(A[i]<0)f=-f;
			if(Math.abs(A[i])<Math.abs(a)) {
				a=A[i];
				index=i;
			}
		}
		if(f==1) {
			long t=Math.min(k,Math.abs(a)/x+1);
			if(a<0) {
				k-=t;
				A[index]+=t*x;
			}else {
				k-=t;
				A[index]-=t*x;
			}
		}
		PriorityQueue<long[]> pq=new PriorityQueue(new Comparator<long[]>() {
			public int compare(long[] a1,long[] a2) {
				return (int)a1[0]-(int)a2[0];
			}
		});
		for(int i=0;i<n;i++) {
			pq.add(new long[] {Math.abs(A[i]),i});
		}
		while(k-->0) {
			long[] q=pq.poll();
			int idx=(int)q[1];
			if(A[idx]<0) {
				A[idx]-=x;
			}else {
				A[idx]+=x;
			}
			pq.add(new long[] {Math.abs(A[idx]),idx});
		}
		for(int i=0;i<n;i++) {
			out.print(A[i]+" ");
		}
	}
}	



class FastReader
{
	BufferedReader br;
	StringTokenizer st;

	public FastReader()
	{
		br=new BufferedReader(new InputStreamReader(System.in));
	}

	public String next() 
	{
		if(st==null || !st.hasMoreElements())
		{
			try {
				st = new StringTokenizer(br.readLine());
			} catch (IOException e) {
				e.printStackTrace();
			}
		}
		return st.nextToken();
	}

	public int nextInt() 
	{
		return Integer.parseInt(next());
	}

	public long nextLong()
	{
		return Long.parseLong(next());
	}
}