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.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class MaximAndArray {

	public static void main(String[] args) throws IOException {
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt(),k=sc.nextInt();
		long x=sc.nextInt();
		pair []a=new pair [n];
		int neg=0;
		for(int i=0;i<n;i++)
		{
			int y=sc.nextInt();
			if(y<0)
				neg++;
			a[i]=new pair(y,i);
		}
		Arrays.sort(a);
		
		PriorityQueue<pair> pq=new PriorityQueue();
		int curr=0;
		while(k-->0)
		{
			pair min;
			if(pq.isEmpty())
				min=a[curr++];
			else if(curr==n || pq.peek().compareTo(a[curr])<=0)
				min=pq.poll();
			else 
				min=a[curr++];
			
			if(min.v<0)
			{
				min.v+=x*(neg%2==1?-1:1); //neg=neg-1.
				
				if(min.v>=0)
					neg--;
			}
			else
			{
				min.v+=x*(neg%2==0?-1:1);
				
				if(min.v<0)
					neg++;
			}
			
			pq.add(min);
			
		}
		long []ans=new long [n];
		for(pair p:a)
			ans[p.idx]=p.v;
		PrintWriter pw=new PrintWriter(System.out);
		for(int i=0;i<n;i++)
			pw.print(ans[i]+" ");
		pw.close();
	
		

	}
	static class pair implements Comparable<pair> 
	{
		long v;
		int idx;
		pair(long x,int y)
		{
			v=x;
			idx=y;
		}
		public String toString()
		{
			return idx+" "+v;
		}
		
public int compareTo(pair o) {
	if(  Math.abs(v)-Math.abs(o.v)==0)
		return 0;
	else if( Math.abs(v)-Math.abs(o.v)>0)
		return 1;
	else return -1;
}
		
	}
	static class Scanner
	{
		BufferedReader br;
		StringTokenizer st;
		public Scanner(InputStream s)
		{
			br=new BufferedReader(new InputStreamReader(s));
		}
		public String nextLine() throws IOException
		{
			return br.readLine();
		}
		public String next() throws IOException
		{
			while(st==null || !st.hasMoreTokens())
				st=new StringTokenizer(br.readLine());
			return st.nextToken();
		}
		public int nextInt() throws IOException
		{
			return Integer.parseInt(next());
			
		}
		public double nextDouble() throws IOException
		{
			return Double.parseDouble(next());
		}
		public boolean ready() throws IOException
		{
			return br.ready();
		}
		public long nextLong() throws IOException
		{
			return Long.parseLong(next());
		}
	}
}
