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.*;


public class Codeforces {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Codeforces o = new Codeforces();
		o.run();
		
	}
		
	I r= new I();
	PrintWriter pw =new PrintWriter(System.out);
//	StringBuilder Ans = new StringBuilder(10000);
	int max = (int)2e5+2;
	long ar[] = new long[max];
	void run(){
		int n,t,k,i,j,x;
		long p,q,u,v;
		n=r.in_i(); v=0;
		k= r.in_i();
		x=r.in_i();
		MinHeap mh = new MinHeap(n+4);
		for(i=0; i<n; i++){
			ar[i] = r.in_l();
			if(ar[i] < 0)
				v++;
			mh.insert(new element(Math.abs(ar[i]), i));
		}
		
		if(v%2==0){
				// try to chng sign of 1 element
			
			element e = mh.extract();
			if( (long)k*x > e.key ){
				//pw.println("Here");
                p = e.key;
				e.key = e.key - (long)Math.ceil((double)e.key/x)*x;
				if(e.key == 0){
					e.key -= x;
				//	k--;
				}
                p -= e.key;
			//	pw.print(e.key);
				e.key = Math.abs(e.key);
				if(ar[e.id] < 0)
					ar[e.id] = e.key;
				else
					ar[e.id] = -e.key;
				v++;
				k -= (int)Math.ceil((double)p/x);
            //    pw.println(k);
				mh.insert(new element(e.key,e.id));
			}
			else{
				e.key -= (long)k*x;
                
				if(ar[e.id] < 0) ar[e.id]=-e.key;
				else ar[e.id] = e.key;
				
			}
		}
		
		if(v%2==1){
			// maximise the product
			while(k > 0){
           //     pw.println("sdad");
				element e = mh.extract();
				e.key += x;
				if(ar[e.id] < 0)
					ar[e.id] -= x;
				else
					ar[e.id] += x;
				mh.insert(new element(e.key, e.id));
				k--;
			}
		}
		for(i=0; i<n; i++)
			pw.print(ar[i]+" ");
        
        pw.close();
	}

	class MinHeap{

	    element heap[];
	    int len;
	    int cap;
	    int pos[];
	 
	    //private static final int FRONT = 1;
	 
	    public MinHeap(int maxsize)
	    {
	        cap = maxsize;
	        len = 0;
	        heap = new element[cap + 1];
	        heap[0] = null;
	        pos = new int[cap+1];
	        Arrays.fill(pos,-1);
	    }

	    void insert (element n)
	    {
	    len = len + 1;
	    heap[len]=n; pos[n.id] = len;
	    int i=len,j;
	  //  change(len, n.key);
	    while( i > 1 && heap[ (j=i>>1) ].key > heap[ i ].key)
	        {
	        swap(j,i);
	        i = j;
	        }
	    }

	    void decrease(int id, int key)
	    {    
	    int i = pos[id],j;
	    heap[i].key = key;
	     while( i > 1 && heap[ (j=i>>1) ].key > heap[ i ].key)
	        {
	        swap(j,i);
	        i = j;
	        }
	    }
	    
	    boolean isEmpty(){
	        return len==0;
	    }

	    void min_heapify (int i)
	    {
	    int left = i<<1, least;          
	    int right = 2*i +1;          //right child
	    if(left<= len && heap[left].key < heap[i].key )
	          least = left;
	    else
	         least = i;
	    if(right <= len && heap[right].key < heap[least].key)
	        least = right;
	    if(least != i )
	    {
	        swap (i, least);
	        min_heapify(least);
	    } 
	    }

	    void swap(int i, int j) {
	        pos[heap[i].id] = j;
	        pos[heap[j].id] = i;
	        element temp=heap[i];
	        heap[i]=heap[j];
	        heap[j]=temp; 

	    }

	    element extract()
	    {
	    element min = heap[1];
	    heap[1] = heap[len];
	    pos[heap[len].id] = 1;
	    pos[min.id] = len;
	    len = len -1;
	    min_heapify(1);
	    return min;
	    }

	    boolean isPresent(int id){
	        if(pos[id] > len || pos[id] == -1)
	            return false;
	        return true;
	    }
	 
	}
	
	class element{
		long key;
		int id;
		element(long x, int y){
			key=x; id=y;
		
        }
		
	}
	
	static class I{
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private SpaceCharFilter filter;
        
        public I() {
                this.stream = System.in;
        }
        
        public int read() {
                if (numChars == -1) {
                        throw new InputMismatchException();
                }
                if (curChar >= numChars) {
                        curChar = 0;
                        try {
                                numChars = stream.read(buf);
                        } catch (IOException e) {
                                throw new InputMismatchException();
                        }
                        if (numChars <= 0) {
                                return -1;
                        }
                }
                return buf[curChar++];
        }
        
        public int in_i() {
                int c = read();
                while (isSpaceChar(c)) {
                        c = read();
                }
                int sgn = 1;
                if (c == '-') {
                        sgn = -1;
                        c = read();
                }
                int res = 0;
                do {
                        if (c < '0' || c > '9') {
                                throw new InputMismatchException();
                        }
                        res = (res<<3) + (res<<1);
                        res += c - '0';
                        c = read();
                } while (!isSpaceChar(c));
                return res * sgn;
        }
        
        public String readString() {
                int c = read();
                while (isSpaceChar(c)) {
                        c = read();
                }
                StringBuilder res = new StringBuilder();
                do {
                        res.appendCodePoint(c);
                        c = read();
                } while (!isSpaceChar(c));
                return res.toString();
        }
        
        public double in_d() {
                int c = read();
                while (isSpaceChar(c)) {
                        c = read();
                }
                int sgn = 1;
                if (c == '-') {
                        sgn = -1;
                        c = read();
                }
                double res = 0;
                while (!isSpaceChar(c) && c != '.') {
                        if (c == 'e' || c == 'E') {
                                return res * Math.pow(10, in_i());
                        }
                        if (c < '0' || c > '9') {
                                throw new InputMismatchException();
                        }
                        res *= 10;
                        res += c - '0';
                        c = read();
                }
                if (c == '.') {
                        c = read();
                        double m = 1;
                        while (!isSpaceChar(c)) {
                                if (c == 'e' || c == 'E') {
                                        return res * Math.pow(10, in_i());
                                }
                                if (c < '0' || c > '9') {
                                        throw new InputMismatchException();
                                }
                                m /= 10;
                                res += (c - '0') * m;
                                c = read();
                        }
                }
                return res * sgn;
        }
        
        public long in_l() {
                int c = read();
                while (isSpaceChar(c)) {
                        c = read();
                }
                int sgn = 1;
                if (c == '-') {
                        sgn = -1;
                        c = read();
                }
                long res = 0;
                do {
                        if (c < '0' || c > '9') {
                                throw new InputMismatchException();
                        }
                        res = (res<<3) + (res<<1);
                        res += c - '0';
                        c = read();
                } while (!isSpaceChar(c));
                return res * sgn;
        }
        
        public boolean isSpaceChar(int c) {
                if (filter != null) {
                        return filter.isSpaceChar(c);
                }
                return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }
        
        public String next() {
                return readString();
        }
        
        public interface SpaceCharFilter {
                public boolean isSpaceChar(int ch);
        }
}
	}

