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.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	public static class Absolute implements Comparable<Absolute>{
		long x;
		int index;
		public Absolute(long x, int index){
			this.x = x;
			this.index = index;
		}
		@Override
		public boolean equals(Object o){
			Absolute a = (Absolute)o;
			return a.index == this.index;
		}
		@Override
		public int compareTo(Absolute a){
			return Long.compare(Math.abs(this.x), Math.abs(a.x));
		}
	}
	public static void main(String[] args){
		InputReader sc = new InputReader(System.in);
		PrintWriter out = new PrintWriter(System.out);
		int n = sc.nextInt();
		int k = sc.nextInt();
		int x = sc.nextInt();
		PriorityQueue<Absolute> set = new PriorityQueue<Absolute>();
		int neg = 0;
		long[] result = new long[n];
		for(int i = 0; i < n; i++){
			long a = sc.nextLong();
			if(a < 0){
				neg++;
			}
			result[i] = a;
			set.add(new Absolute(a, i));
		}
		for(int i = 0; i < k; i++){
			Absolute min = set.remove();
			boolean isNeg = min.x < 0;
			if(neg % 2 == 0){
				//positive
				min.x += (min.x < 0) ? x : (-x);
			}
			else{
				//negative
				min.x += (min.x < 0) ? (-x) : (x);
			}
			if(isNeg && min.x >= 0){
				neg--;
			}
			if(!isNeg && min.x < 0){
				neg++;
			}
			result[min.index] = min.x;
			set.add(min);
		}
		for(long i : result){
			out.print(i + " ");
		}
		out.close();
	}
	
	static class InputReader {
		public BufferedReader reader;
		public StringTokenizer tokenizer;

		public InputReader(InputStream stream) {
			reader = new BufferedReader(new InputStreamReader(stream), 32768);
			tokenizer = null;
		}

		public String next() {
			while (tokenizer == null || !tokenizer.hasMoreTokens()) {
				try {
					tokenizer = new StringTokenizer(reader.readLine());
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
			return tokenizer.nextToken();
		}

		public int nextInt() {
			return Integer.parseInt(next());
		}

		public long nextLong() {
			return Long.parseLong(next());
		}

		public double nextDouble() {
			return Double.parseDouble(next());
		}

		public String nextLine() {
			String str = "";
			try {
				str = reader.readLine();
			} catch (IOException e) {
				e.printStackTrace();
			}

			return str;
		}
	}
}
