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 
//package CF;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class A {
	static int INF = (int) 1e9;

	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		int n = sc.nextInt(), k = sc.nextInt(), x = sc.nextInt();
		long[] a = new long[n];
		int s = 1;
		int min = 0;
		int divMin = -1;
		for (int i = 0; i < a.length; i++) {
			a[i] = sc.nextInt();
			s *= a[i] >= 0 ? 1 : -1;
			if (Math.abs(a[i]) < Math.abs(a[min]))
				min = i;
			if (a[i] % x == 0 && (divMin == -1 || Math.abs(a[i]) < Math.abs(a[divMin])))
				divMin = i;
		}
		
		if (s > 0) {
			long m = (Math.abs(a[min]) + x) / x;
			
			if (m <= k) {
				a[min] += (a[min] >= 0 ? -1 : 1) * 1l * x * m;
				k -= m;
				s = -1;
			} else if (divMin != -1 && Math.abs(a[divMin]) / x <= k) {
				k -= Math.abs(a[divMin]) / x;
				a[divMin] = 0;
			}
		}
		PriorityQueue<Pair> pq = new PriorityQueue<>();
		for (int i = 0; i < a.length; i++) {
			pq.add(new Pair(Math.abs(a[i]), a[i] >= 0 ? 1 : -1, i));
		}
		for (int i = 0; i < k; i++) {
			Pair small = pq.remove();
			long tmp = s > 0 ? small.val - x : small.val + x;
			pq.add(new Pair(tmp, small.sign, small.idx));
		}
		while (!pq.isEmpty()) {
			Pair tmp = pq.remove();
			a[tmp.idx] = tmp.val * tmp.sign;
		}
		for (long i : a)
			out.print(i + " ");
		out.flush();
		out.close();
	}

	static class Pair implements Comparable<Pair> {
		long val;
		int sign, idx;

		public Pair(long v, int s, int i) {
			val = v;
			sign = s;
			idx = i;
		}

		@Override
		public int compareTo(Pair o) {
			// TODO Auto-generated method stub
			return val > o.val ? 1 : -1;
		}

		public String toString() {
			return val + " " + sign + " " + idx;
		}
	}

	static class Scanner {
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream s) {
			br = new BufferedReader(new InputStreamReader(s));
		}

		public Scanner(FileReader fileReader) {
			br = new BufferedReader(fileReader);
		}

		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

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

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

		public String nextLine() throws IOException {
			return br.readLine();
		}

		public boolean ready() throws IOException {
			return br.ready();
		}
	}
}