Đổi dấu

Cho $n$ số nguyên $a_1,a_2,\dots ,a_n$, với $n$ lẻ. Bạn được phép đổi dấu một số phần tử tuỳ ý (có thể tất cả, có thể không đổi phần tử nào), tức là thay $a_i$ bởi $-a_i$.

Gọi dãy thu được là $b_1,b_2,\dots ,b_n$ (mỗi $b_i$ bằng $a_i$ hoặc $-a_i$). Hãy đổi dấu sao cho đồng thời thoả mãn:

1. Có ít nhất $\frac{n-1}{2}$ hiệu liền kề $b_{i+1}-b_i$ (với $i=1,2,\dots ,n-1$) không âm.
2. Có ít nhất $\frac{n-1}{2}$ hiệu liền kề $b_{i+1}-b_i$ (với $i=1,2,\dots ,n-1$) không dương.

Một hiệu bằng $0$ được tính cho cả hai điều kiện. Với ràng buộc đã cho, luôn tồn tại ít nhất một cách đổi dấu hợp lệ. Nếu có nhiều đáp án, in ra bất kỳ đáp án nào.

Dữ liệu vào

• Dòng đầu chứa số nguyên $t$ là số bộ dữ liệu.
• Mỗi bộ dữ liệu gồm hai dòng:
  • Dòng thứ nhất chứa số nguyên lẻ $n$.
  • Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra một dòng gồm $n$ số nguyên $b_1,b_2,\dots ,b_n$ thoả mãn yêu cầu.

Ràng buộc

• $1\le t\le 500$
• $3\le n\le 99$, $n$ lẻ
• $-{10}^9\le a_i\le {10}^9$
• Tổng $n$ trên tất cả các bộ dữ liệu không vượt quá ${10}^4$

Ví dụ