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

public class D374 {
	public static void main(String[] args) {
		MyScanner scan = new MyScanner();
		
		int N =scan.nextInt(), K = scan.nextInt(), X = scan.nextInt();
		
		boolean[] neg = new boolean[N];
		int negCount = 0;
		long[] list = new long[N];
		int min = 0;
		for(int i=0;i<N;i++){
			list[i] = scan.nextLong();
			if(list[i]<0){
				negCount++;
				neg[i]=true;
				list[i]*=-1;
			}
			min = list[i]<list[min]?i:min;
		}
		
		if(negCount%2==0){
			while(K>0&&list[min]>=0){
				list[min]-=X;
				K--;
			}
			if(list[min]<0){
				neg[min] = !neg[min];
			}
			list[min]= Math.abs(list[min]);
		}
		
		PriorityQueue<Pair> q = new PriorityQueue<>(new Comparator<Pair>() {
			public int compare(Pair p1, Pair p2) {
				double d1 = p1.d, d2 = p2.d;
				double delta1 = Math.abs(d1-Math.log(p1.val+X));
				double delta2 = Math.abs(d2-Math.log(p2.val+X));
				return -Double.compare(delta1, delta2);
			}
		});
		for(int i=0;i<N;i++){
			q.add(new Pair(Math.log(list[i]), list[i], i));
		}
		
		while(K>0){
			K--;
			Pair p = q.poll();
			p.val+=X;
			p.d = Math.log(p.val);
			q.add(p);
		}
		
		long[] sol = new long[N];
		while(!q.isEmpty()){
			Pair p = q.poll();
			sol[p.idx] = p.val;
		}
		
		PrintWriter out = new PrintWriter(System.out);
		for(int i=0;i<N;i++){
			if(neg[i])sol[i]*=-1;
			out.print(sol[i]+" ");
		}
		out.println();
		out.close();
	}
	private static class Pair {
		double d;
		long val;
		int idx;
		public Pair(double d, long val, int idx){
			this.val=val;
			this.d=d;this.idx=idx;
		}
	}
	private static class MyScanner {
		BufferedReader br;
		StringTokenizer st;
		public MyScanner() {br = new BufferedReader(new InputStreamReader(System.in));}
		String next(){
			while(st==null||!st.hasMoreElements()){
				try{st = new StringTokenizer(br.readLine());}
				catch(IOException e){e.printStackTrace();}
			}return st.nextToken();
		}
		int nextInt() {return Integer.parseInt(next());}
		long nextLong(){return Long.parseLong(next());}
		double nextDouble(){return Double.parseDouble(next());}
	}
}
