题目描述

给定 $n$ 个整数 $a_1, a_2, \dots, a_n$，其中 $n$ 是奇数。你可以选择将其中一些（可以全部或一个也不选）数的符号翻转。你需要进行符号翻转，使得满足以下两个条件：

1. 至少有 $\frac{n - 1}{2}$ 个相邻差值 $a_{i + 1} - a_i$（$i = 1, 2, \dots, n - 1$）大于等于 $0$。
2. 至少有 $\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}$ 个是非正数。

可以证明，在给定的限制条件下，至少存在一种满足要求的符号翻转方案。如果有多种方案，你可以输出任意一种。

说明/提示

在第一个测试样例中，差值 $(-4) - (-2) = -2$ 是非正数，而 $3 - (-4) = 7$ 是非负数。

在第二个测试样例中，不需要翻转任何符号。所有 $4$ 个差值都等于 $0$，既是非正数也是非负数。

在第三个测试样例中，$7 - (-4)$ 和 $4 - (-6)$ 是非负数，而 $(-4) - (-2)$ 和 $(-6) - 7$ 是非正数。

由 ChatGPT 4.1 翻译

样例

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