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 *a*_{i} either with *a*_{i} + *x* or with *a*_{i} - *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. ) can reach, if Maxim would apply no more than *k* operations to it. Please help him in that.

The first line of the input contains three integers *n*, *k* and *x* (1 ≤ *n*, *k* ≤ 200 000, 1 ≤ *x* ≤ 10^{9}) — 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 *a*_{1}, *a*_{2}, ..., *a*_{n} () — the elements of the array found by Maxim.

Print *n* integers *b*_{1}, *b*_{2}, ..., *b*_{n} in the only line — the array elements after applying no more than *k* operations to the array. In particular, 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.

提交代码