Maxim and Array

题意翻译

$n$ 个数，最多进行$k$ 次操作，每次可以$+x$ 或$-x$ ,求当$\Pi_{i-1}^na_i$ 最小时的每个元素 **输入：** 第一行：$n,k,x(1\leq n,k\leq 200000,1\leq x\leq 10^9)$ 第二行:$a_i$ **输出：** 一行：$\Pi_{i-1}^na_i$ 最小时的每个元素 感谢@Fheiwn 提供的翻译

题目描述

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<=200000,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.

输入输出样例

输入样例 #1

5 3 1
5 4 3 5 2

输出样例 #1

5 4 3 5 -1 

输入样例 #2

5 3 1
5 4 3 5 5

输出样例 #2

5 4 0 5 5 

输入样例 #3

5 3 1
5 4 4 5 5

输出样例 #3

5 1 4 5 5 

输入样例 #4

3 2 7
5 4 2

输出样例 #4

5 11 -5