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.*;
import java.util.*;
import java.math.*;
import java.util.concurrent.*;

public final class maxim_and_array
{
    static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
	static FastScanner sc=new FastScanner(br);
    static PrintWriter out=new PrintWriter(System.out);
	static Random rnd=new Random();
	static int n;
	static long x;
	
	static long[] get(Pair[] a,int k)
	{
		PriorityQueue<Pair> pq=new PriorityQueue<>();
		
		for(int i=0;i<n;i++)
		{
			pq.add(new Pair(a[i].idx,a[i].val));
		}
		
		while(k>0)
		{
			Pair curr=pq.poll();
			
			if(curr.val<0)
			{
				curr.val-=x;
			}
			
			else
			{
				curr.val+=x;  
			}
			
			pq.add(new Pair(curr.idx,curr.val));
			
			k--;
		}
		
		long[] res=new long[n];
		
		for(Pair p:pq)
		{
			res[p.idx]=p.val;
		}
		
		return res;
	}
	
    public static void main(String args[]) throws Exception
    {
		n=sc.nextInt();int k=sc.nextInt();x=sc.nextLong();int neg=0;Pair[] a=new Pair[n];
		
		for(int i=0;i<n;i++)
		{
			a[i]=new Pair(i,sc.nextLong());
			
			if(a[i].val<0)
			{
				neg++;
			}
		}
		
		if(neg%2==0)
		{
			Arrays.sort(a);long[] res=new long[n];
			
			if(a[0].val<0 && a[0].val+(k*x)>=0)
			{
				while(a[0].val<0)
				{
					a[0].val+=x;k--;
				}
				
				res=get(a,k);
			}
			
			else if(a[0].val>=0 && a[0].val-(k*x)<0)
			{
				while(a[0].val>=0)
				{
					a[0].val-=x;k--;
				}
				
				res=get(a,k);
			}
			
			else
			{
				PriorityQueue<Pair> pq=new PriorityQueue<>();
				
				for(int i=0;i<n;i++)
				{
					pq.add(new Pair(a[i].idx,-a[i].val));
				}
				
				while(k>0)
				{
					Pair curr=pq.poll();
					
					curr.val+=x;
					
					pq.add(new Pair(curr.idx,curr.val));
					
					k--;
				}
				
				for(Pair p:pq)
				{
					res[p.idx]=-p.val;
				}
			}
			
			for(int i=0;i<n;i++)
			{
				out.print(res[i]+" ");
			}
			
			out.println("");
		}
		
		else
		{
			long[] res=get(a,k);
			
			for(int i=0;i<n;i++)
			{
				out.print(res[i]+" ");
			}
			
			out.println("");
		}
		
		out.close();
    }
}

class Pair implements Comparable<Pair>
{
	int idx;long val;
	
	public Pair(int idx,long val)
	{
		this.idx=idx;this.val=val;
	}
	
	public int compareTo(Pair x)
	{
		return Long.compare(Math.abs(this.val),Math.abs(x.val));
	}
}
class FastScanner
{
    BufferedReader in;
    StringTokenizer st;

    public FastScanner(BufferedReader in) {
        this.in = in;
    }
	
    public String nextToken() throws Exception {
        while (st == null || !st.hasMoreTokens()) {
            st = new StringTokenizer(in.readLine());
        }
        return st.nextToken();
    }
	
	public String next() throws Exception {
		return nextToken().toString();
	}
	
    public int nextInt() throws Exception {
        return Integer.parseInt(nextToken());
    }

    public long nextLong() throws Exception {
        return Long.parseLong(nextToken());
    }

    public double nextDouble() throws Exception {
        return Double.parseDouble(nextToken());
    }
}