You are given a sequence of integers $A_1, A_2, \dots, A_N$.
You should choose an arbitrary (possibly empty) subsequence of $A$ and multiply each element of this subsequence by $-1$. The resulting sequence should satisfy the following condition: the sum of elements of any contiguous subsequence with length greater than 1 is strictly positive.
You should minimise the sum of elements of the resulting sequence. Find one such sequence with the minimum possible sum.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains a single integer $N$.
- The second line contains $N$ space-separated integers $A_1, A_2, \dots, A_N$.

-----Output-----
For each test case, print a single line containing $N$ space-separated integers $B_1, B_2, \dots, B_N$. For each valid $i$, $B_i$ must be equal to either $A_i$ (the sign of this element did not change) or $-A_i$ (the sign of this element changed).
If there is more than one answer, you may output any one.

-----Constraints-----
- $1 \le T \le 10^5$
- $2 \le N \le 10^5$
- $1 \le A_i \le 10^9$ for each valid $i$
- the sum of $N$ for all test cases does not exceed $5 \cdot 10^5$

-----Subtasks-----
Subtask #1 (20 points):
- $1 \le T \le 200$
- $2 \le N \le 10$
Subtask #2 (30 points):
- $1 \le T \le 1,000$
- $N \le 2,000$
Subtask #3 (50 points): original constraints

-----Example Input-----
4
4
4 3 1 2
6
1 2 2 1 3 1
5
10 1 2 10 5
4
1 2 1 2

-----Example Output-----
4 3 -1 2
-1 2 2 -1 3 -1
10 -1 2 10 -5
1 2 -1 2

-----Explanation-----
Example case 1: If we change only the sign of $A_3$, we get a sequence $\{4, 3, -1, 2\}$ with sum $8$. This sequence is valid because the sums of all its contiguous subsequences with length $> 1$ are positive. (For example, the sum of elements of the contiguous subsequence $\{A_3, A_4\}$ equals $-1 + 2 = 1 > 0$.)
There are only two valid sequences $\{4, 3, -1, 2\}$ and $\{4, 3, 1, 2\}$ with sums $8$ and $10$ respectively, so this sequence has the smallest possible sum.
For instance, the sequence $\{4, -3, 1, 2\}$ isn't valid, because the sum of $\{A_2, A_3, A_4\}$ equals $-3 + 1 + 2 = 0 \le 0$.

Difficulty: interview

Starter code:

Solutions:
"""
4
4
4 3 1 2
6
1 2 2 1 3 1
5
10 1 2 10 5
4
1 2 1 2
"""
tests = int(input())

for _ in range(tests):

 n = int(input())
 ls = list(map(int, input().split()))

 if ls[0] < ls[1]:
  ls[0] = -ls[0]

 if ls[-1] < ls[-2]:
  ls[-1] = -ls[-1]

 for i in range(1, n - 1):
  if ls[i] < ls[i - 1] and ls[i] < ls[i + 1]:
   ls[i] = -ls[i]
   '''
      if i > 1 and ls[i - 2] < 0 and ls[i] - ls[i-2] >= ls[i-1]:
       # There can be only one!
       if -ls[i-2] < ls[i]:
        # We win!
        ls[i-2] = -ls[i-2]
        ls[i] = -ls[i]
        #else:
        # They win!
        # Do nothing
      else:
       # We both can go negative
       ls[i] = -ls[i]
      '''
   
 #print(ls)
 
 ind = 1

 while ind < n - 1:

  started = False
  pos = []
  while ind < n - 1 and ls[ind] + ls[ind - 1] + ls[ind + 1] <= 0:
   if not started:
    pos.append(ind - 1)
    pos.append(ind + 1)
    started = True
   else:
    pos.append(ind + 1)
   ind += 2

  #print(pos,ls)

  if started:
   rec = [0] * (len(pos) + 1)

   for i in pos:
    ls[i] = -ls[i]

   rec[0] = 0
   rec[1] = ls[pos[0]]

   for i in range(2, len(pos) + 1):
    rec[i] = max(rec[i - 1], ls[pos[i - 1]] + rec[i - 2])

   itr = len(pos)
   while itr > 0:
    if itr == 1 or rec[itr] == ls[pos[itr - 1]] + rec[itr - 2]:
     ls[pos[itr - 1]] = -ls[pos[itr - 1]]
     itr -= 2
    else:
     itr -= 1

  ind += 1

 for i in ls:
  print(i, end = ' ')
 print() 

  



"""
4
4
4 3 1 2
6
1 2 2 1 3 1
5
10 1 2 10 5
4
1 2 1 2
"""
tests = int(input())

for _ in range(tests):

 n = int(input())
 ls = list(map(int, input().split()))

 if ls[0] < ls[1]:
  ls[0] = -ls[0]

 if ls[-1] < ls[-2]:
  ls[-1] = -ls[-1]

 for i in range(1, n - 1):
  if ls[i] < ls[i - 1] and ls[i] < ls[i + 1]:
   ls[i] = -ls[i]
   '''
      if i > 1 and ls[i - 2] < 0 and ls[i] - ls[i-2] >= ls[i-1]:
       # There can be only one!
       if -ls[i-2] < ls[i]:
        # We win!
        ls[i-2] = -ls[i-2]
        ls[i] = -ls[i]
        #else:
        # They win!
        # Do nothing
      else:
       # We both can go negative
       ls[i] = -ls[i]
      '''
   
 #print(ls)
 
 ind = 1

 while ind < n - 1:

  started = False
  pos = []
  while ind < n - 1 and ls[ind] + ls[ind - 1] + ls[ind + 1] <= 0:
   if not started:
    pos.append(ind - 1)
    pos.append(ind + 1)
    started = True
   else:
    pos.append(ind + 1)
   ind += 2

  if started:
   rec = [0] * (len(pos) + 1)

   for i in pos:
    ls[i] = -ls[i]

   rec[0] = 0
   rec[1] = ls[pos[0]]

   for i in range(2, len(pos) + 1):
    rec[i] = max(rec[i - 1], ls[pos[i - 1]] + rec[i - 2])

   itr = len(pos)
   while itr > 0:
    if itr == 1 or rec[itr] == ls[pos[itr - 1]] + rec[itr - 2]:
     ls[pos[itr - 1]] = -ls[pos[itr - 1]]
     itr -= 2
    else:
     itr -= 1

  ind += 1

 for i in ls:
  print(i, end = ' ')
 print() 

  



"""
4
4
4 3 1 2
6
1 2 2 1 3 1
5
10 1 2 10 5
4
1 2 1 2
"""
tests = int(input())

for _ in range(tests):

 n = int(input())
 ls = list(map(int, input().split()))

 if ls[0] < ls[1]:
  ls[0] = -ls[0]

 if ls[-1] < ls[-2]:
  ls[-1] = -ls[-1]

 for i in range(1, n - 1):
  if ls[i] < ls[i - 1] and ls[i] < ls[i + 1]:
   ls[i] = -ls[i]
   '''
      if i > 1 and ls[i - 2] < 0 and ls[i] - ls[i-2] >= ls[i-1]:
       # There can be only one!
       if -ls[i-2] < ls[i]:
        # We win!
        ls[i-2] = -ls[i-2]
        ls[i] = -ls[i]
        #else:
        # They win!
        # Do nothing
      else:
       # We both can go negative
       ls[i] = -ls[i]
      '''
   
 #print(ls)
 
 ind = 1

 while ind < n - 1:

  started = False
  pos = []
  while ind < n - 1 and ls[ind] + ls[ind - 1] + ls[ind + 1] <= 0:
   if not started:
    pos.append(ind - 1)
    pos.append(ind + 1)
    started = True
   else:
    pos.append(ind + 1)
   ind += 2

  if started:
   rec = [0] * (len(pos) + 1)

   for i in pos:
    ls[i] = -ls[i]

   rec[0] = 0
   rec[1] = ls[pos[0]]

   for i in range(2, len(pos) + 1):
    rec[i] = max(rec[i - 1], ls[pos[i - 1]] + rec[i - 2])

   itr = len(pos)
   while itr > 0:
    if itr == 1 or rec[itr] == ls[pos[itr - 1]] + rec[itr - 2]:
     ls[pos[itr - 1]] = -ls[pos[itr - 1]]
     itr -= 2
    else:
     itr -= 1

  ind += 1

 for i in ls:
  print(i, end = ' ')
 print()