Maxim and Array
Contest: Codeforces Round 374 (Div. 2)
Difficulty rating: 2000
Tags: constructive algorithms, data structures, greedy, math

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. $$\prod_{i=1}^{n}a_{i}$$) can reach, if Maxim would apply no more than k operations to it. Please help him in that.

Input format:
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 ($${ \big | } a _ { i } { \big | } \leq 1 0 ^ { 9 }$$) — the elements of the array found by Maxim.

Output format:
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, $$a_i \equiv b_i \mod x$$ 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.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
5 3 1
5 4 3 5 2

Example output:
5 4 3 5 -1

Example input:
5 3 1
5 4 3 5 5

Example output:
5 4 0 5 5

Editorial:
Main idea: we act greedily, trying to make the best possible answer every action (each time we choose an action with minimum possible product after it).
Detailed explanation:
1. While we have zeroes in our array, we have to get rid of them, changing each of them exactly one time. Also we keep the quantity of negative numbers — we need it to make the product negative after changing the last zero. Let m be the number of zeroes in the array. If m > k, then we cannot make the product negative or positive (it will always be equal to 0), so any sequence of operations will lead to a correct answer. However, if m ≤ k, then we are able to come to negative product (if the number of negative elements was even, then we subtract x from one zero and add it to all other zeroes; if the number of negative elements was odd, then we can just add x to all zeroes).
2. If current product is still positive, then we want to change the sign of exactly one element. Its absolute value has to be minimal: suppose we have two elements a and b, |a| < |b|; let's prove that if we change b's sign, then our answer is wrong. Let m be the minimum number of operations required to change b's sign. If we perform m operations with b, then the absolute value of a won't change, and absolute value of b will become x·m - |b|. If, on the other hand, we perform m operations with a (this may not be optimal, but now we need to prove that if we change b, then the result will be worse), then the absolute value of a will become x·m - |a|, the absolute value of b won't change. The product becomes negative, so we need to maximize the product of absolute values. And then x·m - |a| > x·m - |b| and |b| > |a|, so if we change b, then the product of absolute values will be less than if we change a.
3. Now, until we have performed k operations, we choose a number with minimum absolute value and enlarge it (add x if this number if positive, subtract if negative). Let's prove that the answer will be optimal. Suppose that this algorithm chooses a on some iteration, but we can't get optimal answer if we change a. This means that we can't change a after this iteration at all (we can reorder our operations in an arbitrary way, and the answer won't change). Suppose we have to change b instead, and |b| > |a|. Let's consider the sequence of operations leading to the optimal answer when we choose b, and replace change of b with change of a, and let the product of all remaining numbers (the whole array excluding a and b after all operations) be c. If we change a, the total product will be  - (|a| + x)·(|b| + x·m)·|c|, and if we change b, we get  - |a|·(|b| + x·(m + 1))·|c| (m is the number of times we change b). Now |a| < |b| + x·m, so (|a| + x)·(|b| + x·m) - |a|·(|b| + x·(m + 1)) = |b| + x·m - |a| > 0, so the absolute value of total product will be greater if we change a. This proves that we won't come to unoptimal answer if we change a.
Time complexity: $${\mathcal O}\left((n+k)\log n\right)$$ if we use a data structure similar to set or priority_queue to get the number with minimal absolute value. Memory complexity: O(n).