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