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.PriorityQueue;
import java.util.StringTokenizer;
public class A {
	static PrintWriter pw;
	public static void main(String[] args)throws Throwable {
		MyScanner sc=new MyScanner();
		pw=new PrintWriter(System.out,true);
		
		int n=sc.nextInt(),k=sc.nextInt(),x=sc.nextInt();
		pair [] a=new pair [n];
		PriorityQueue<pair> q=new PriorityQueue<pair>();
		int neg=0;
		for(int i=0;i<n;i++){
			int y=sc.nextInt();
			if(y<0)
				neg^=1;
			a[i]=new pair(y,i);
			q.add(new pair(Math.abs(a[i].x), i));
		}
		while(k-->0){
			pair p=q.poll();
			if(a[p.y].x<0)
				neg^=1;
			if(neg==1){
				a[p.y].x+=x;
			}else{
				a[p.y].x-=x;
			}
			if(a[p.y].x<0)
				neg^=1;
			q.add(new pair(Math.abs(a[p.y].x), p.y));
		}
		
		int [] ans=new int [n];
		for(int i=0;i<n;i++)
			ans[a[i].y]=i;
		for(int i=0;i<n;i++)
			pw.print(a[ans[i]].x+" ");
		pw.println();
		pw.flush();
		pw.close();
	}
	
	static class pair implements Comparable<pair>{
		long x;
		int y;
		pair(long a,int b){
			x=a;y=b;
		}
		public String toString(){
			return ""+x;
		}
		
		public int compareTo(pair o) {
			return x-o.x>0? 1 : -1;
		}
	}
	
	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());
	      }
	 
	      String nextLine(){
	          String str = "";
		  try {
		     str = br.readLine();
		  } catch (IOException e) {
		     e.printStackTrace();
		  }
		  return str;
	      }

	   }
}