Nick 收到了一个很棒的整数数组 $$$a=[a_1, a_2, \dots, a_n]$$$ 作为他母亲送给他的 $$$5$$$ 生日礼物。他已经打算探索它的各种属性,但在打开包装后,他非常失望,因为它的元素的乘积 $$$a_1 \cdot a_2 \cdot \dots a_n$$$ 对他来说似乎不够大。
他正准备扔掉阵法,但他的母亲却安抚了他。她告诉他,在执行以下操作后,该数组不会被破坏:选择任何索引 $$$i$$$ ($$$1 \le i \le n$$$) 并执行 $$$a_i := -a_i - 1$$$。
例如,在对索引为 $$$i=1$$$ 和 $$$i=3$$$ 的元素应用此操作后,他可以将数组 $$$[3, -1, -4, 1]$$$ 更改为数组 $$$[-4, -1, 3, 1]$$$。
Kolya 立即明白,有时可以大幅增加数组整数的乘积。现在他决定他想要获得一个具有最大可能的整数乘积的数组,仅使用对其元素的此操作(可能零次,一次或多次,只要他想要),不禁止对同一索引多次执行此操作。
帮助 Kolya 并打印元素 $$$a_1 \cdot a_2 \cdot \dots a_n$$$ 的最大可能乘积的数组,仅使用此操作按某种顺序即可接收该数组。
如果有多个答案,请打印其中任何一个。
输入
第一行包含整数 $$$n$$$ ($$$1 \leq n \leq 10^{5}$$$) — 数组中整数的数量。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^{6} \leq a_i \leq 10^{6}$$$) — 数组的元素
输出
打印 $$$n$$$ 数字 — 数组中的元素与仅使用此操作以某种顺序从给定数组中接收的元素的最大可能乘积。
如果有多个答案,请打印其中任何一个。
示例
输入 #1
4 2 2 2 2
输出 #1
-3 -3 -3 -3
输入 #2
1 0
输出 #2
0
输入 #3
3 -3 -3 2
输出 #3
-3 -3 2