На свой \(5\) день рождения Коля получил от мамы в подарок новенький массив \(a=[a_1, a_2, \dots, a_n]\)! Он уже собирался хорошенько изучить его различные свойства, однако распаковав массив, он заметно расстроился, так как произведение его элементов \(a_1 \cdot a_2 \cdot \dots a_n\) показалось ему недостаточно большим.
Он уже было собирался выбросить массив в окно, но мама сказала ему, что массив не очень испортится, если он сделает следующую операцию: выберет произвольный индекс \(i\) (\(1 \le i \le n\)) и выполнит присваивание \(a_i := -a_i - 1\).
Например он может превратить массив \([3, -1, -4, 1]\) в массив \([-4, -1, 3, 1]\) применив эту операцию к индексам \(i=1\) и \(i=3\).
Коля сразу понял, что в некоторых случаях таким образом можно заметно увеличить произведение чисел массива. На следующий день после дня рождения он решил, что хочет получить массив с как можно большим произведением чисел, используя только вышеупомянутую операцию (возможно, ноль, один либо несколько раз), не запрещено применять эту операцию несколько раз к одному элементу.
Помогите маленькому Коле и выведите массив, который может быть получен из исходного многократным применением вышеупомянутой операции, имеющий максимально возможное произведение элементов \(a_1 \cdot a_2 \cdot \dots a_n\).
Если существуют несколько ответов, выведите любой из них.
Выходные данные
Выведите через пробел \(n\) чисел — массив, который может быть получен из исходного многократным применением вышеупомянутой операции, имеющий максимально возможное произведение чисел.
Если существуют несколько ответов, выведите любой из них.