A. Изменение знаков
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам даны $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$, где $$$n$$$ нечетно. Вы можете поменять знаки некоторых (возможно, всех или ни одного) из них. Вы хотите поменять знаки таким образом, чтобы выполнялись следующие условия:

  • Не менее $$$\frac{n - 1}{2}$$$ среди разностей соседних $$$a_{i + 1} - a_i$$$ для $$$i = 1, 2, \dots, n - 1$$$ больше либо равны $$$0$$$.
  • Не менее $$$\frac{n - 1}{2}$$$ среди разностей соседних $$$a_{i + 1} - a_i$$$ для $$$i = 1, 2, \dots, n - 1$$$ меньше либо равны $$$0$$$.

Найдите любой подходящий способ поменять знаки. Можно показать, что при данных ограничениях всегда существует хотя бы один выбор знаков, который удовлетворяет требуемому условию. Если существует несколько решений, выведите любое из них.

Входные данные

Ввод состоит из нескольких наборов входных данных. В первой строке записано целое число $$$t$$$ ($$$1 \le t \le 500$$$)  — количество наборов входных данных. Описание наборов входных данных приведено ниже.

Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$3 \le n \le 99$$$, $$$n$$$ нечетно)  — количество целых чисел, данных вам.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$)   — сами числа.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$10000$$$.

Выходные данные

Для каждого набора входных данных выведите $$$n$$$ целых чисел $$$b_1, b_2, \dots, b_n$$$, соответствующих целым числам после изменения знаков. $$$b_i$$$ должно быть равно либо $$$a_i$$$, либо $$$-a_i$$$, а также среди разностей соседних $$$b_{i + 1} - b_i$$$ для $$$i = 1, \dots, n - 1$$$, по крайней мере $$$\frac{n - 1}{2}$$$ должна быть неотрицательными, и хотя бы $$$\frac{n - 1}{2}$$$ должна быть неположительными.

Можно показать, что при данных ограничениях всегда существует хотя бы один выбор знаков, который удовлетворяет требуемому условию. Если существует несколько решений, выведите любое из них.

Пример
Входные данные
5
3
-2 4 3
5
1 1 1 1 1
5
-2 4 7 -6 4
9
9 7 -4 -2 1 -3 9 -4 -5
9
-4 1 9 4 8 9 5 1 -9
Выходные данные
-2 -4 3
1 1 1 1 1
-2 -4 7 -6 4
-9 -7 -4 2 1 -3 -9 -4 -5
4 -1 -9 -4 -8 -9 -5 -1 9
Примечание

В первом наборе входных данных разница $$$(-4) - (-2) = -2$$$ неположительна, а разница $$$3 - (-4) = 7$$$ неотрицательна.

Во втором наборе входных данных нам не нужно менять знаки. Все $$$4$$$ разности равны $$$0$$$, и являются как неположительными, так и неотрицательными.

В третьем наборе входных данных $$$7 - (-4)$$$ и $$$4 - (-6)$$$ неотрицательны, а $$$(-4) - (-2)$$$ и $$$(-6) - 7$$$ неположительны.