| Codeforces Round 374 (Div. 2) |
|---|
| Закончено |
Недавно Максим нашел никому не нужный массив n целых чисел. Ему сразу пришла в голову идея для изменения этого массива: он придумал целое положительное число x и решил прибавлять или вычитать его из произвольных элементов массива. Формально, за одну операцию Максим выбирает целое число i (1 ≤ i ≤ n), и меняет i-й элемент массива ai либо на ai + x, либо на ai - x. Обратите внимание, что операцию можно применять более одного раза к элементу на одной и той же позиции.
Максим — любопытный минималист, поэтому он хочет узнать, какое минимальное значение может принять произведение всех элементов массива (то есть 
), если Максим применит к нему не более k операций. Помогите ему в этом.
В первой строке входных данных содержится три целых числа n, k и x (1 ≤ n, k ≤ 200 000, 1 ≤ x ≤ 109) — количество элементов в массиве, максимальное количество операций и число, придуманное Максимом, соответственно.
Во второй строке содержится n целых чисел a1, a2, ..., an (
) — элементы массива, который нашел Максим.
В единственной строке выведите n целых чисел b1, b2, ..., bn — элементы массива после применения к нему не более чем k описанных операций. В частности, 
должно быть верным для всех 1 ≤ i ≤ n, а произведение всех элементов массива должно быть минимально возможным.
Если ответов несколько, выведите любой.
5 3 1
5 4 3 5 2
5 4 3 5 -1
5 3 1
5 4 3 5 5
5 4 0 5 5
5 3 1
5 4 4 5 5
5 1 4 5 5
3 2 7
5 4 2
5 11 -5
