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 MaximAndArray {

    static class Pair implements Comparable<Pair> {
	long x;
	int idx;

	Pair(long a, int b) {
	    x = a;
	    idx = b;
	}

	@Override
	public String toString() {
	    return x + " " + idx;
	}

	@Override
	public int compareTo(Pair p) {
	    return Long.compare(Math.abs(x), Math.abs(p.x));
	}
    }

    public static void main(String[] args) throws IOException {
	MyScanner sc = new MyScanner(System.in);
	PrintWriter out = new PrintWriter(System.out);
	long n = sc.nextLong(), k = sc.nextLong(), x = sc.nextLong();
	PriorityQueue<Pair> pq = new PriorityQueue<>();
	int cnt = 0;
	for (int i = 0; i < n; i++) {
	    int a = sc.nextInt();
	    pq.add(new Pair(a, i));
	    if (a < 0)
		cnt++;
	}
	for (int i = 0; i < k; i++) {
	    Pair p = pq.poll();
	    if ((cnt & 1) == 0) {
		if (p.x < 0) {
		    pq.add(new Pair(p.x + x, p.idx));
		    if (p.x + x >= 0)
			cnt--;
		}
		else {
		    pq.add(new Pair(p.x - x, p.idx));
		    if (p.x - x < 0)
			cnt++;
		}
	    }
	    else {
		if (p.x >= 0)
		    pq.add(new Pair(p.x + x, p.idx));
		else
		    pq.add(new Pair(p.x - x, p.idx));
	    }
	}
	long[] res = new long[(int) n];
	while (!pq.isEmpty())
	    res[pq.peek().idx] = pq.poll().x;
	out.print(res[0]);
	for (int i = 1; i < n; i++)
	    out.print(" " + res[i]);
	out.println();
	out.flush();
	out.close();
    }

    static class MyScanner {
	BufferedReader br;
	StringTokenizer st;

	MyScanner(InputStream in) {
	    br = new BufferedReader(new InputStreamReader(in));
	}

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

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

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