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: HARD
Tags: Dynamic programming
Skill types: Dynamic programming

Starter code:

Solutions:
T = int(input())
for l in range(T):
	N = int(input())
	arr = input().split(' ')
	signs = []
	for p in range(N):
		signs.append(0)
		arr[p] = int(arr[p])
	count = 0
	if arr[0] < arr[1]:
		signs[0] = -1
		count += 1
	if arr[N - 1] < arr[N - 2]:
		signs[-1] = -1
		count += 1
	for k in range(1, N - 1):
		if arr[k] < arr[k + 1] and arr[k] < arr[k - 1]:
			signs[k] = -1
			count += 1

	def find(ptr):
		ptr += 1
		while ptr < N and signs[ptr] == 0:
			ptr += 1
		if ptr >= N:
			ptr = -1
		return ptr

	def sum(start, end):
		summer = start + 1
		sum = 0
		while summer != end:
			sum += arr[summer]
			summer += 1
		return sum
	if count >= 2:
		a = find(-1)
		b = find(a)
		c = find(b)
		while c != -1:
			if arr[a] + arr[b] >= sum(a, b):
				if arr[b] + arr[c] >= sum(b, c):
					ar = []
					ptr = a
					include_index = []
					while find(ptr) < N and find(ptr) != -1 and (arr[ptr] + arr[find(ptr)] >= sum(ptr, find(ptr))):
						ar.append(arr[ptr])
						include_index.append(ptr)
						ptr = find(ptr)
					ar.append(arr[ptr])
					include_index.append(ptr)
					max_include = []
					max_exclude = []
					for u in range(len(ar)):
						max_include.append(0)
						max_exclude.append(0)
					max_include[0] = ar[0]
					max_exclude[0] = 0
					Max = ar[0]
					for i in range(1, len(ar)):
						max_include[i] = max_exclude[i - 1] + ar[i]
						max_exclude[i] = max(max_include[i - 1], max_exclude[i - 1])
						Max = max(max_include[i], max_exclude[i])
					u = len(ar) - 1
					while u > 0:
						if max_include[u] <= max_exclude[u]:
							signs[include_index[u]] = 0
							u -= 1
						else:
							signs[include_index[u - 1]] = 0
							u -= 2
					a = ptr
					b = find(a)
					if b == -1:
						c = -1
					else:
						c = find(b)
					continue
				if arr[b] + arr[c] < sum(b, c):
					if arr[a] < arr[b]:
						signs[a] = 0
						a = b
					else:
						signs[b] = 0
					b = c
					c = find(c)
					continue
			if arr[a] + arr[b] < sum(a, b):
				a = b
				b = c
				c = find(c)
		if c == -1 and b != -1:
			if arr[a] + arr[b] >= sum(a, b):
				if arr[a] <= arr[b]:
					signs[a] = 0
				else:
					signs[b] = 0
	meaw = ''
	for p in range(N):
		if signs[p] == -1:
			meaw += str(-1 * arr[p]) + ' '
		else:
			meaw += str(arr[p]) + ' '
	print(meaw)


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]
	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()


def is_candidate(i, a):
	return (i == 0 or a[i] < a[i - 1]) and (i == len(a) - 1 or a[i] < a[i + 1])

def solve_chain(indecies, a):
	(last, here) = (0, 0)
	(last_i, here_i) = ([], [])
	for i in indecies:
		if last + a[i] > here:
			(last, here) = (here, last + a[i])
			last_i.append(i)
			(last_i, here_i) = (here_i, last_i)
		else:
			(last, here) = (here, here)
			(last_i, here_i) = (here_i, here_i[:])
	for i in here_i:
		a[i] = -a[i]
for t in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().strip().split()]
	indecies = []
	last_candidate = True
	for i in range(n):
		if is_candidate(i, a):
			if len(indecies) > 0 and i > 1 and (a[i - 2] + a[i] < a[i - 1]):
				solve_chain(indecies, a)
				indecies = []
			indecies.append(i)
			last_candidate = True
		elif last_candidate:
			last_candidate = False
		elif len(indecies) > 0:
			solve_chain(indecies, a)
			indecies = []
	if len(indecies) > 0:
		solve_chain(indecies, a)
	print(*a)


t = int(input())
for m in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	for i in range(n):
		if i == 0:
			if arr[i] < arr[i + 1]:
				arr[i] = -arr[i]
		elif i == n - 1:
			if arr[i] < arr[i - 1]:
				arr[i] = -arr[i]
		elif arr[i] < arr[i + 1] and arr[i] < arr[i - 1]:
			arr[i] = -arr[i]
	ind = -1
	index_arr = []
	for i in range(n):
		if ind == -1:
			if arr[i] < 0:
				index_arr.append(i)
				ind = i
		elif arr[i] < 0:
			if i - ind == 2:
				if arr[i - 1] + arr[i] + arr[ind] > 0:
					index_arr.append(i)
				ind = i
			else:
				index_arr.append(i)
				ind = i
	leng = len(index_arr)
	for i in range(leng):
		grap = {}
		prev_inc = {}
		incl = 0
		excl = 0
		end_index = 0
		if i != leng - 1:
			for j in range(index_arr[i], index_arr[i + 1], 2):
				if arr[j] > 0:
					break
				if j == index_arr[i]:
					temp = incl
					incl = excl + -arr[j]
					excl = temp
					grap[j] = None
					prev_inc[j] = j
					end_index = j
				else:
					temp = incl
					if incl < excl + -arr[j]:
						incl = excl + -arr[j]
						end_index = j
						if j - 4 >= index_arr[i]:
							grap[j] = prev_inc[j - 4]
							prev_inc[j] = j
						else:
							grap[j] = None
							prev_inc[j] = j
					else:
						grap[j] = None
						prev_inc[j] = prev_inc[j - 2]
					excl = temp
		else:
			for j in range(index_arr[i], n, 2):
				if arr[j] > 0:
					break
				if j == index_arr[i]:
					temp = incl
					incl = excl + -arr[j]
					excl = temp
					prev_inc[j] = j
					end_index = j
					grap[j] = None
				else:
					temp = incl
					if incl < excl + -arr[j]:
						incl = excl + -arr[j]
						end_index = j
						if j - 4 >= index_arr[i]:
							grap[j] = prev_inc[j - 4]
							prev_inc[j] = j
						else:
							grap[j] = None
							prev_inc[j] = j
					else:
						grap[j] = None
						prev_inc[j] = prev_inc[j - 2]
					excl = temp
		grap2 = {}
		start = end_index
		while 1:
			grap2[start] = 1
			if grap[start] == None:
				break
			else:
				start = grap[start]
		if i != leng - 1:
			for j in range(index_arr[i], index_arr[i + 1], 2):
				if arr[j] > 0:
					break
				try:
					lpo = grap2[j]
				except:
					arr[j] = -arr[j]
		else:
			for j in range(index_arr[i], n, 2):
				if arr[j] > 0:
					break
				try:
					lpo = grap2[j]
				except:
					arr[j] = -arr[j]
	for i in range(n):
		print(str(arr[i]) + ' ', end='')
	print()


from math import inf

def mylogic(n, _a):
	a = _a[:]
	if n == 2:
		if a[0] > a[1]:
			a[1] *= -1
		elif a[1] > a[0]:
			a[0] *= -1
		print(str(a[0]), str(a[1]))
		return
	ppp = [[0, 0] for i in range(n)]
	npp = [[0, 0] for i in range(n)]
	pnp = [[0, 0] for i in range(n)]
	ppn = [[0, 0] for i in range(n)]
	npn = [[0, 0] for i in range(n)]
	ppp[0] = [a[0], 0]
	ppp[1] = [ppp[0][0] + a[1], 0]
	ppp[2] = [ppp[1][0] + a[2], 0]
	npp[0] = [inf, 1]
	npp[1] = [a[1] - a[0] if a[1] > a[0] else inf, 1]
	npp[2] = [npp[1][0] + a[2], 1]
	pnp[0] = [a[0], 2]
	pnp[1] = [a[0] - a[1] if a[0] > a[1] else inf, 2]
	pnp[2] = [pnp[1][0] + a[2] if a[2] > a[1] else inf, 2]
	ppn[0] = [a[0], 3]
	ppn[1] = [a[0] + a[1], 3]
	ppn[2] = [ppn[1][0] - a[2] if a[1] > a[2] else inf, 3]
	npn[0] = [inf, 4]
	npn[1] = [a[1] - a[0] if a[1] > a[0] else inf, 4]
	npn[2] = [npn[1][0] - a[2] if a[1] > a[2] and a[1] > a[0] + a[2] else inf, 4]
	for i in range(3, n):
		if ppp[i - 1][0] > npp[i - 1][0]:
			ppp[i] = [npp[i - 1][0] + a[i], 1]
		else:
			ppp[i] = [ppp[i - 1][0] + a[i], 0]
		npp[i] = [pnp[i - 1][0] + a[i], 2]
		if a[i] > a[i - 1]:
			if ppn[i - 1][0] > npn[i - 1][0]:
				pnp[i] = [npn[i - 1][0] + a[i], 4]
			else:
				pnp[i] = [ppn[i - 1][0] + a[i], 3]
		else:
			pnp[i] = [inf, -1]
		if a[i - 1] > a[i]:
			if npp[i - 1][0] > ppp[i - 1][0]:
				ppn[i] = [ppp[i - 1][0] - a[i], 0]
			else:
				ppn[i] = [npp[i - 1][0] - a[i], 1]
		else:
			ppn[i] = [inf, -1]
		if a[i - 1] > a[i] and a[i - 1] > a[i] + a[i - 2]:
			npn[i] = [pnp[i - 1][0] - a[i], 2]
		else:
			npn[i] = [inf, -1]
	value = inf
	m = -1
	it = 0
	minit = -1
	for l in [ppp, npp, pnp, ppn, npn]:
		if value > l[-1][0]:
			value = l[-1][0]
			minit = it
			m = l
		it += 1
	if n > 3 and minit > 2:
		a[-1] *= -1
	m = m[-1][1]
	data = [True, None]
	if m == 0:
		data = [True, ppp]
	elif m == 1:
		data = [True, npp]
	elif m == 2:
		data = [True, pnp]
	elif m == 3:
		data = [False, ppn]
	else:
		data = [False, npn]
	for i in range(n - 1, 3, -1):
		if not data[0]:
			a[i - 1] *= -1
		m = data[1][i - 1][1]
		if m == 0:
			data = [True, ppp]
		elif m == 1:
			data = [True, npp]
		elif m == 2:
			data = [True, pnp]
		elif m == 3:
			data = [False, ppn]
		else:
			data = [False, npn]
	if data[1] == ppp:
		pass
	elif data[1] == npp:
		a[0] *= -1
	elif data[1] == pnp:
		a[1] *= -1
	elif data[1] == ppn:
		a[2] *= -1
	else:
		a[0] *= -1
		a[2] *= -1
	print(' '.join([str(e) for e in a]))

def brute(n, _a):
	minsum = inf
	ans = None
	for i in range(0, 2 ** n):
		a = _a[:]
		x = i
		for j in range(n - 1, -1, -1):
			if x & 1:
				a[j] *= -1
			x >>= 1
		flag = True
		for j in range(0, n - 1):
			if a[j] + a[j + 1] <= 0:
				flag = False
				break
		if flag:
			for j in range(0, n - 2):
				if a[j] + a[j + 1] + a[j + 2] <= 0:
					flag = False
					break
		if flag:
			if sum(a) < minsum:
				minsum = sum(a)
				ans = a[:]
	return ans
t = int(input())
while t > 0:
	n = int(input())
	a = [int(i) for i in input().split()]
	mylogic(n, a)
	t -= 1


T = int(input())
for i in range(T):
	N = int(input())
	Alist = list(map(int, input().split()))
	newList = []
	count = 0
	sign = []
	newindex = []
	for j in range(N):
		sign.append(0)
	if Alist[0] < Alist[1]:
		newList.append(-Alist[0])
		newindex.append(0)
		sign[0] = 1
	else:
		newList.append(Alist[0])
		newindex.append(0)
		count += 1
	for j in range(1, N - 1):
		if Alist[j] < Alist[j - 1] and Alist[j] < Alist[j + 1]:
			newList.append(-Alist[j])
			newindex.append(j)
			sign[j] = 1
			count = 0
		else:
			count += 1
			if count == 1:
				newList.append(Alist[j])
				newindex.append(j)
			else:
				newList[-1] += Alist[j]
	if Alist[N - 1] < Alist[N - 2]:
		newList.append(-Alist[N - 1])
		newindex.append(N - 1)
		sign[N - 1] = 1
	else:
		count += 1
		if count == 1:
			newList.append(Alist[N - 1])
			newindex.append(N - 1)
		else:
			newList[-1] += Alist[N - 1]
	N1 = len(newList)
	ptr = 0
	if newList[0] > 0:
		ptr = 1
	while True:
		ll = []
		while True:
			if ptr + 2 <= N1 - 1 and abs(newList[ptr]) + abs(newList[ptr + 2]) >= newList[ptr + 1]:
				ll.append(ptr)
				if ptr + 4 > N1 - 1:
					ll.append(ptr + 2)
				elif abs(newList[ptr + 2]) + abs(newList[ptr + 4]) < newList[ptr + 3]:
					ll.append(ptr + 2)
				ptr += 2
			else:
				break
		pointer = []
		sums = []
		for j in range(len(ll)):
			sums.append(abs(newList[ll[j]]))
		for j in range(len(ll)):
			pointer.append(-1)
		ans = []
		if len(ll) > 3:
			sums[2] += sums[0]
			pointer[2] = 0
			for j in range(3, len(ll)):
				if sums[j - 2] > sums[j - 3]:
					sums[j] += sums[j - 2]
					pointer[j] = j - 2
				else:
					sums[j] += sums[j - 3]
					pointer[j] = j - 3
			if sums[-1] > sums[-2]:
				start = len(ll) - 1
			else:
				start = len(ll) - 2
			ans.append(ll[start])
			while pointer[start] != -1:
				start = pointer[start]
				ans.append(ll[start])
			ans.reverse()
			newans = list(set(ll) - set(ans))
		elif len(ll) == 3:
			sums[2] += sums[0]
			if sums[2] > sums[1]:
				ans.append(ll[1])
			else:
				ans.append(ll[0])
				ans.append(ll[2])
		elif len(ll) == 2:
			if sums[1] > sums[0]:
				ans.append(ll[0])
			else:
				ans.append(ll[1])
		if len(ll) > 3:
			for j in range(len(newans)):
				sign[newindex[newans[j]]] = 0
		else:
			for j in range(len(ans)):
				sign[newindex[ans[j]]] = 0
		ptr += 2
		if ptr > N1 - 1:
			break
	for j in range(N):
		if sign[j] == 1:
			Alist[j] *= -1
	print(*Alist)


T = int(input())
for q in range(0, T):
	N = int(input())
	s = [int(x) for x in input().split()]
	R = [1] * N
	s = [s[0] + 1] + s + [s[-1] + 1]
	L = []
	for i in range(1, len(s) - 1):
		if s[i] < s[i - 1] and s[i] < s[i + 1]:
			L.append(i - 1)
	s = s[1:len(s) - 1]
	G = []
	for i in range(0, len(L) - 1):
		if L[i] != L[i + 1] - 2:
			G.append(0)
		elif s[L[i]] + s[L[i + 1]] < s[L[i] + 1]:
			G.append(0)
		else:
			G.append(1)
	if len(L) > 0:
		C = [L[0]]
		K = [s[L[0]]]
		for i in range(0, len(G)):
			if G[i] == 0:
				R[L[i + 1]] = -1
				incl = 0
				excl = 0
				L1 = []
				L2 = []
				G1 = []
				for j in range(0, len(K)):
					F1 = L1
					old_incl = incl
					if incl != max(excl + K[j], incl):
						L1 = G1 + [j]
					else:
						L1 = L1
					incl = max(excl + K[j], incl)
					excl = old_incl
					G1 = F1
				L1.append(len(C) + 100)
				temp = 0
				for j in range(0, len(C)):
					if j == L1[temp]:
						temp = temp + 1
					else:
						L2.append(j)
				L1 = L1[:len(L1) - 1]
				for j in range(0, len(L1)):
					R[C[L1[j]]] = -1
				for j in range(0, len(L2)):
					R[C[L2[j]]] = 1
				C = [L[i + 1]]
				K = [s[L[i + 1]]]
			else:
				C.append(L[i + 1])
				K.append(s[L[i + 1]])
		incl = 0
		excl = 0
		L1 = []
		L2 = []
		G1 = []
		for i in range(0, len(K)):
			F1 = L1
			old_incl = incl
			if incl != max(excl + K[i], incl):
				L1 = G1 + [i]
			else:
				L1 = L1
			incl = max(excl + K[i], incl)
			excl = old_incl
			G1 = F1
		L1.append(len(C) + 100)
		temp = 0
		for i in range(0, len(C)):
			if i == L1[temp]:
				temp = temp + 1
			else:
				L2.append(i)
		L1 = L1[:len(L1) - 1]
		for i in range(0, len(L1)):
			R[C[L1[i]]] = -1
		for i in range(0, len(L2)):
			R[C[L2[i]]] = 1
		for i in range(0, N):
			print(s[i] * R[i], end=' ')
		print(' ')
	else:
		for i in range(0, N):
			print(s[i], end=' ')
		print(' ')


import itertools

def binseq(k):
	return [''.join(x) for x in itertools.product('01', repeat=k)]

def sumx(arr, x):
	arr2 = []
	for i in range(len(arr) - x + 1):
		sum1 = 0
		for j in range(x):
			sum1 += arr[i + j]
		arr2.append(sum1)
	return arr2

def recPath(arr, n):
	arr3 = []
	for i in range(n - 3):
		arr3.append(0)
	arr3.append(arr[-1] + arr[-3])
	arr3.append(arr[-2])
	arr3.append(arr[-1])
	arr4 = []
	for i in range(n):
		arr4.append(0)
	arr4[-3] = n - 1
	for i in range(len(arr) - 4, 0, -1):
		if arr3[i + 2] > arr3[i + 3]:
			val = arr3[i + 2]
			ch = i + 2
		else:
			val = arr3[i + 3]
			ch = i + 3
		arr3[i] = arr[i] + val
		arr4[i] = ch
	if arr3[1] > arr3[2]:
		stP = 1
	else:
		stP = 2
	return (arr4, stP, arr3)

def checkThree(arr):
	for i in range(len(arr) - 2):
		if arr[i] + arr[i + 1] + arr[i + 2] <= 0:
			return False
	return True
for i in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	if n == 2:
		if arr[0] > arr[1]:
			arr[1] = -arr[1]
		elif arr[0] < arr[1]:
			arr[0] = -arr[0]
		print(' '.join((str(e) for e in arr)))
		continue
	arro = list(arr)
	if arr[1] > arr[0]:
		arr[0] = -arr[0]
	for f in range(1, n - 1):
		if arr[f] < arr[f + 1] and arr[f - 1] > arr[f]:
			arr[f] = -arr[f]
	if arr[-1] < arr[-2]:
		arr[-1] = -arr[-1]
	if n == 3:
		if arr[0] < 0:
			if arr[2] < 0:
				if arr[0] + arr[1] + arr[2] < 0:
					if arr[0] < arr[2]:
						arr[2] = -arr[2]
					else:
						arr[0] = -arr[0]
		print(' '.join((str(e) for e in arr)))
		continue
	if n < 1:
		maxm = 10000000
		maxarr = []
		noOfNeg = 0
		arrneg = []
		for j in range(len(arr)):
			if arr[j] < 0:
				noOfNeg += 1
				arrneg.append(j)
		arrbin = binseq(noOfNeg)
		for j in range(2 ** noOfNeg):
			current = arrbin[j]
			arro = list(arr)
			for k in range(noOfNeg):
				place = arrneg[k]
				if current[k] == '0':
					arro[place] = -arro[place]
			ans = checkThree(arro)
			if ans == True and sum(arro) < maxm:
				maxm = sum(arro)
				maxarr = arro
		print(' '.join((str(e) for e in maxarr)))
	else:
		arrTotal = []
		arrTotal2 = []
		arrtemp = [0]
		arrtemp2 = [0]
		for j in range(n - 2):
			if arr[j] + arr[j + 1] + arr[j + 2] <= 0:
				if -arrtemp[-1] != arr[j]:
					arrtemp.append(-arr[j])
					arrtemp2.append(j)
				arrtemp.append(-arr[j + 2])
				arrtemp2.append(j + 2)
			if arr[j] + arr[j + 1] + arr[j + 2] > 0 and arr[j] < 0 and (arr[j + 2] < 0):
				arrTotal.append(arrtemp)
				arrTotal2.append(arrtemp2)
				arrtemp2 = [0]
				arrtemp = [0]
			if arr[j + 1] > 0 and arr[j + 2] > 0:
				arrTotal.append(arrtemp)
				arrTotal2.append(arrtemp2)
				arrtemp2 = [0]
				arrtemp = [0]
		if len(arrtemp) > 1:
			arrTotal.append(arrtemp)
			arrTotal2.append(arrtemp2)
		if n > 3:
			if arr[3] + arr[2] + arr[1] > 0 and arr[2] + arr[1] + arr[0] > 0 and (arr[1] < 0) and (arro[1] > 0):
				arro[1] = -arro[1]
			if arr[2] + arr[1] + arr[0] > 0 and arr[0] < 0 and (arro[0] > 0):
				arro[0] = -arro[0]
			for j in range(2, n - 2):
				if arr[j - 2] + arr[j - 1] + arr[j] > 0 and arr[j - 1] + arr[j] + arr[j + 1] > 0 and (arr[j] + arr[j + 1] + arr[j + 2] > 0) and (arr[j] < 0) and (arro[j] > 0):
					arro[j] = -arro[j]
			if arr[-4] + arr[-3] + arr[-2] > 0 and arr[-3] + arr[-2] + arr[-1] > 0 and (arr[-2] < 0) and (arro[-2] > 0):
				arro[-2] = -arro[-2]
			if arr[-3] + arr[-2] + arr[-1] > 0 and arr[-1] < 0 and (arro[-1] > 0):
				arro[-1] = -arro[-1]
		elif n == 2:
			arro = arr
		elif arr[0] < 0 and arr[2] < 0 and (arr[0] + arr[2] + arr[1] < 0):
			arro[0] = arr[0]
		else:
			arro = arr
		if n > 3:
			index = 0
			for j in range(len(arrTotal)):
				if len(arrTotal[j]) > 1:
					(arr4, stp, arrsum) = recPath(arrTotal[j], len(arrTotal[j]))
					while stp != 0:
						val = arrTotal[j][stp]
						index = arrTotal2[j][stp]
						while index < n:
							if arro[index] == val and arro[index] > 0:
								arro[index] = -arro[index]
								break
							index += 1
						stp = arr4[stp]
		print(' '.join((str(e) for e in arro)))


t = int(input())
for i in range(t):
	n = int(input())
	a = [float('inf')]
	temp = list(map(int, input().split()))
	temp.append(float('inf'))
	a.extend(temp)
	for j in range(1, n + 1):
		if a[j] < a[j - 1] and a[j] < a[j + 1]:
			a[j] = -1 * a[j]
	arr = []
	j = 1
	c = 0
	while j <= n - 1:
		if a[j] + a[j + 1] + a[j + 2] <= 0:
			c = 1
			if len(arr) == 0:
				arr.append(j)
				arr.append(j + 2)
			else:
				arr.append(j + 2)
			j += 1
		elif c == 1:
			if len(arr) > 3:
				best = []
				mindis = []
				for i in range(len(arr)):
					best.append(-1)
					mindis.append(a[arr[i]])
				best[-3] = len(arr) - 1
				mindis[-3] += mindis[-1]
				for i in range(len(arr) - 4, -1, -1):
					if mindis[i + 2] < mindis[i + 3]:
						mindis[i] += mindis[i + 2]
						best[i] = i + 2
					else:
						mindis[i] += mindis[i + 3]
						best[i] = i + 3
				if mindis[0] < mindis[1]:
					g = 0
					for i in range(len(arr)):
						if i != g:
							a[arr[i]] = -1 * a[arr[i]]
						else:
							g = best[g]
				else:
					g = 1
					for i in range(len(arr)):
						if i != g:
							a[arr[i]] = -1 * a[arr[i]]
						else:
							g = best[g]
			else:
				(se, so) = (0, 0)
				for i in range(len(arr)):
					if i & 1 == 0:
						se += a[arr[i]]
					else:
						so += a[arr[i]]
				if se > so:
					for i in range(0, len(arr), 2):
						a[arr[i]] = -1 * a[arr[i]]
				else:
					for i in range(1, len(arr), 2):
						a[arr[i]] = -1 * a[arr[i]]
			arr = []
			c = 0
		j += 1
	if c == 1:
		if len(arr) > 3:
			best = []
			mindis = []
			for i in range(len(arr)):
				best.append(-1)
				mindis.append(a[arr[i]])
			best[-3] = len(arr) - 1
			mindis[-3] += mindis[-1]
			for i in range(len(arr) - 4, -1, -1):
				if mindis[i + 2] < mindis[i + 3]:
					mindis[i] += mindis[i + 2]
					best[i] = i + 2
				else:
					mindis[i] += mindis[i + 3]
					best[i] = i + 3
			if mindis[0] < mindis[1]:
				g = 0
				for i in range(len(arr)):
					if i != g:
						a[arr[i]] = -1 * a[arr[i]]
					else:
						g = best[g]
			else:
				g = 1
				for i in range(len(arr)):
					if i != g:
						a[arr[i]] = -1 * a[arr[i]]
					else:
						g = best[g]
		else:
			(se, so) = (0, 0)
			for i in range(len(arr)):
				if i & 1 == 0:
					se += a[arr[i]]
				else:
					so += a[arr[i]]
			if se > so:
				for i in range(0, len(arr), 2):
					a[arr[i]] = -1 * a[arr[i]]
			else:
				for i in range(1, len(arr), 2):
					a[arr[i]] = -1 * a[arr[i]]
	print(*a[1:-1])


t = int(input())
inf = 10 ** 14 + 1
for rr in range(t):
	n = int(input())
	a = list(map(int, input().strip().split()))
	dp = [[inf, inf] for i in range(n)]
	dp[0][0] = a[0]
	dp[0][1] = -a[0]
	for i in range(1, n):
		if a[i] - a[i - 1] > 0:
			dp[i][0] = min(dp[i][0], dp[i - 1][1] + a[i])
		dp[i][0] = min(dp[i][0], dp[i - 1][0] + a[i])
		if i == 1:
			if a[i - 1] - a[i] > 0:
				dp[i][1] = dp[i - 1][0] - a[i]
		else:
			if a[i - 1] - a[i] - a[i - 2] > 0:
				dp[i][1] = min(dp[i][1], dp[i - 2][1] + a[i - 1] - a[i])
			if a[i - 1] - a[i] > 0:
				dp[i][1] = min(dp[i][1], dp[i - 2][0] + a[i - 1] - a[i])
	mn = min(dp[n - 1][0], dp[n - 1][1])
	ans = []
	ls = 1
	if dp[n - 1][0] == mn:
		ans.append(a[n - 1])
	else:
		ans.append(-a[n - 1])
		ls = -1
	i = n - 2
	while i >= 0:
		if i == 0:
			if ls == 1:
				if dp[i][1] + a[i + 1] == dp[i + 1][0]:
					ans.append(-a[i])
					ls = -1
				elif dp[i][0] + a[i + 1] == dp[i + 1][0]:
					ans.append(a[i])
			else:
				ans.append(a[i])
		elif ls == 1:
			if dp[i][1] + a[i + 1] == dp[i + 1][0] and a[i + 1] - a[i] > 0:
				ans.append(-a[i])
				ls = -1
			elif dp[i][0] + a[i + 1] == dp[i + 1][0]:
				ans.append(a[i])
		elif dp[i - 1][1] + a[i] - a[i + 1] == dp[i + 1][1] and a[i] - a[i - 1] - a[i + 1] > 0:
			ans.append(a[i])
			ans.append(-a[i - 1])
			i -= 1
		elif dp[i - 1][0] + a[i] - a[i + 1] == dp[i + 1][1] and a[i] - a[i + 1] > 0:
			ans.append(a[i])
			ans.append(a[i - 1])
			i -= 1
			ls = 1
		i -= 1
	st = ''
	for j in range(n - 1, -1, -1):
		st += str(ans[j]) + ' '
	print(st)


class Node:

	def __init__(self, i, last):
		self.i = i
		self.last = last

def is_candidate(i, a):
	return (i == 0 or a[i] < a[i - 1]) and (i == len(a) - 1 or a[i] < a[i + 1])

def solve_chain(indecies, a):
	(last, here) = (0, 0)
	(last_i, here_i) = (None, None)
	for i in indecies:
		if last + a[i] > here:
			(last, here) = (here, last + a[i])
			last_i = Node(i, last_i)
			(last_i, here_i) = (here_i, last_i)
		else:
			(last, here) = (here, here)
			(last_i, here_i) = (here_i, here_i)
	while here_i is not None:
		a[here_i.i] = -a[here_i.i]
		here_i = here_i.last
for t in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().strip().split()]
	indecies = []
	last_candidate = True
	for i in range(n):
		if is_candidate(i, a):
			if len(indecies) > 0 and i > 1 and (a[i - 2] + a[i] < a[i - 1]):
				solve_chain(indecies, a)
				indecies = []
			indecies.append(i)
			last_candidate = True
		elif last_candidate:
			last_candidate = False
		elif len(indecies) > 0:
			solve_chain(indecies, a)
			indecies = []
	if len(indecies) > 0:
		solve_chain(indecies, a)
	print(*a)


from pprint import pprint

def f(i, N, A):
	if i >= N:
		return 0
	val = A[i] + f(i + 1, N, A)
	if (i == N - 1 or A[i] < A[i + 1]) and (i == 0 or A[i] < A[i - 1]):
		if i < N - 2:
			if -A[i] + A[i + 1] - A[i + 2] > 0:
				val = min(-A[i] + A[i + 1] + f(i + 2, N, A), val)
			else:
				val = min(-A[i] + A[i + 1] + A[i + 2] + f(i + 3, N, A), val)
		else:
			val = min(-A[i] + (A[i + 1] if i != N - 1 else 0), val)
	print(i, val)
	return val

def dp(N, A):
	total = sum(A)
	Mem = [total for n in range(N + 1)]
	Mem[N] = 0
	for i in reversed(range(N)):
		val = A[i] + Mem[i + 1]
		if (i == N - 1 or A[i] < A[i + 1]) and (i == 0 or A[i] < A[i - 1]):
			if i < N - 2:
				if -A[i] + A[i + 1] - A[i + 2] > 0:
					val = min(-A[i] + A[i + 1] + Mem[i + 2], val)
				else:
					val = min(-A[i] + A[i + 1] + A[i + 2] + Mem[i + 3], val)
			else:
				val = min(-A[i] + (A[i + 1] if i != N - 1 else 0), val)
		Mem[i] = val
	result = A[:]
	i = 0
	while i < N:
		val = A[i] + Mem[i + 1]
		if (i == N - 1 or A[i] < A[i + 1]) and (i == 0 or A[i] < A[i - 1]):
			if i < N - 2:
				if -A[i] + A[i + 1] - A[i + 2] > 0:
					if -A[i] + A[i + 1] + Mem[i + 2] <= val:
						result[i] = -result[i]
						i = i + 2
					else:
						i = i + 1
				elif -A[i] + A[i + 1] + A[i + 2] + Mem[i + 3] <= val:
					result[i] = -result[i]
					i = i + 3
				else:
					i = i + 1
			elif -A[i] + (A[i + 1] if i != N - 1 else 0) <= val:
				result[i] = -result[i]
				i = N
			else:
				i = i + 1
		else:
			i = i + 1
	return result

def ff(i, AA, N, A):
	if i == N:
		prefixSum = {-1: 0, -2: 0}
		for i in range(N):
			prefixSum[i] = AA[i] + prefixSum[i - 1]
		for i in range(N):
			for j in range(i + 1, N):
				if prefixSum[j] - prefixSum[i - 1] <= 0:
					return (sum(A), A)
		return (sum(AA), AA)
	(val1, val2) = (ff(i + 1, AA + [-A[i]], N, A), ff(i + 1, AA + [A[i]], N, A))
	if val1[0] < val2[0]:
		return val1
	else:
		return val2
T = int(input())
for _ in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	result = dp(N, A)
	for a in result:
		print(a, end=' ')
	print()


T = int(input())
while T > 0:
	N = int(input())
	A = list()
	A = list(map(int, input().strip().split(' ')))
	B = [0] * N
	for i in range(0, N):
		B[i] = A[i]
	if A[0] < A[1]:
		B[0] = -1 * A[0]
	if A[N - 1] < A[N - 2]:
		B[N - 1] = -1 * A[N - 1]
	for i in range(1, N - 1):
		if A[i] < A[i + 1] and A[i] < A[i - 1]:
			B[i] = -1 * A[i]
			i = i + 1
	z1 = 1
	if z1 == 1:
		i = -1
		while i < N:
			i = i + 1
			j = i
			while N - i > 2:
				temp = 0
				temp = B[i] + B[i + 1] + B[i + 2]
				if temp > 0:
					break
				else:
					i = i + 2
			if i != j:
				inc = [0] * ((i - j) // 2 + 2)
				exc = [0] * ((i - j) // 2 + 2)
				l = 1
				k = j
				while k <= i:
					B[k] = -1 * B[k]
					inc[l] = exc[l - 1] + A[k]
					if exc[l - 1] > inc[l - 1]:
						exc[l] = exc[l - 1]
					else:
						exc[l] = inc[l - 1]
					k = k + 2
					l = l + 1
				if inc[l - 1] > exc[l - 1]:
					max = inc[l - 1]
				else:
					max = exc[l - 1]
				p = i
				q = j
				l = (i - j) // 2 + 1
				while p >= q:
					if inc[l] == max:
						max = max - A[p]
						B[p] = -1 * B[p]
						p = p - 2
						l = l - 1
					p = p - 2
					l = l - 1
	for i in range(0, N):
		print(B[i], end=' ')
	print()
	T = T - 1


def find_max_sum(arr):
	incl = 0
	excl = 0
	incll = []
	excll = []
	new_excll = []
	for (index, i) in enumerate(arr):
		if excl > incl:
			new_excl = excl
			new_excll = excll
		else:
			new_excl = incl
			new_excll = incll
		incl = excl + i
		incll = excll + [index]
		excl = new_excl
		excll = new_excll
	if excl > incl:
		return excll
	else:
		return incll
t = int(input())
while t:
	n = int(input())
	l = list(map(int, input().strip().split()))
	lr = [int(10000000000.0)] + l + [int(10000000000.0)]
	l1 = [0 for i in range(n + 2)]
	l1[0] = 2
	l1[n + 1] = 2
	for k in range(1, n + 1):
		if lr[k - 1] > lr[k] and lr[k + 1] > lr[k]:
			l1[k] = -1
		elif lr[k - 1] + lr[k + 1] < lr[k]:
			l1[k] = 2
		else:
			l1[k] = 1
	lt = []
	st = -1
	for u in range(1, n + 2):
		if l1[u] == 1:
			if l1[u - 1] != -1:
				if st != -1:
					a = find_max_sum(lt)
					for u2 in a:
						lr[2 * u2 + st] = -lr[2 * u2 + st]
				st = -1
				lt = []
			else:
				continue
		elif l1[u] == 2:
			if st != -1:
				a = find_max_sum(lt)
				for u2 in a:
					lr[2 * u2 + st] = -lr[2 * u2 + st]
			st = -1
			lt = []
		else:
			if st == -1:
				st = u
			lt.append(lr[u])
	print(' '.join(map(str, lr[1:n + 1])))
	t = t - 1


t = int(input())
inf = 10 ** 16
for _ in range(t):
	n = int(input())
	A = [int(x) for x in input().split()]
	C = [0]
	for a in A:
		C.append(C[-1] + a)
	A.append(inf)
	poss = []
	for i in range(n):
		if A[i - 1] > A[i] and A[i] < A[i + 1]:
			poss.append(i)
	del A[-1]
	if poss:
		D = [[None] * 2 for _ in range(len(poss))]
		D[0][0] = 0
		D[0][1] = A[poss[0]]
		for i in range(len(poss) - 1):
			D[i + 1][0] = max(D[i][0], D[i][1])
			D[i + 1][1] = D[i][C[poss[i + 1]] - C[poss[i]] - 2 * A[poss[i]] - A[poss[i + 1]] > 0 and D[i][1] >= D[i][0]] + A[poss[i + 1]]
		if D[-1][1] >= D[-1][0]:
			h = 1
			A[poss[-1]] *= -1
		else:
			h = 0
		for i in reversed(range(len(D) - 1)):
			if h:
				if D[i][1] + abs(A[poss[i + 1]]) == D[i + 1][1] and (not D[i][0] + abs(A[poss[i + 1]]) == D[i + 1][1]):
					h = 1
					A[poss[i]] *= -1
				else:
					h = 0
			elif D[i][1] == D[i + 1][0]:
				h = 1
				A[poss[i]] *= -1
			else:
				h = 0
	print(*A)


T = int(input())
INF = 10 ** 20

def solve(s):
	n = len(s)
	prv = [None for i in range(n + 1)]
	p = 0
	q = -INF
	for i in range(n):
		prv[i] = p < q
		(p, q) = (max(p, q), p + s[i])
	prv[n] = p < q
	v = n
	res = [0] * n
	while v > 0:
		if prv[v]:
			res[v - 1] = 1
			v -= 2
		else:
			v -= 1
	return res
ans = []
for _ in range(T):
	N = int(input())
	(*A,) = map(int, input().split())
	B = [0] * N
	B[0] = A[0] < A[1]
	B[-1] = A[-2] > A[-1]
	for i in range(1, N - 1):
		B[i] = A[i - 1] > A[i] < A[i + 1]
	cur = 0
	res = 0
	while cur < N:
		while cur < N and (not B[cur]):
			cur += 1
		if cur == N:
			break
		s = [A[cur]]
		r = [cur]
		while cur + 2 < N and B[cur + 2] and (A[cur] + A[cur + 2] >= A[cur + 1]):
			cur += 2
			s.append(A[cur])
			r.append(cur)
		cur += 1
		rs = solve(s)
		for (i, f) in zip(r, rs):
			if f:
				A[i] = -A[i]
	ans.append(' '.join(map(str, A)))
print(*ans, sep='\n')


t = int(input())
for e in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	a.append(10 ** 18 + 5)
	b = []
	sub = 0
	i = 0
	swi = [False for i in range(n)]
	while i < n:
		temp = []
		flag = False
		while a[i] >= a[i + 1] or (a[i] >= a[i - 1] and i != 0):
			i += 1
			if i >= n:
				flag = True
				break
		temp.append(i)
		i += 2
		if flag:
			break
		while i < n and a[i] < a[i - 1] and (a[i] < a[i + 1]):
			temp.append(i)
			i += 2
		i += 1
		if len(temp) == 1:
			sub += a[temp[0]]
			swi[temp[0]] = True
		else:
			b.append(temp)
	for alt in b:
		dp = [[0, -1] for i in range(len(alt))]
		dp[0] = [a[alt[0]], -1]
		if a[alt[0]] + a[alt[0] + 2] < a[alt[0] + 1]:
			dp[1] = [dp[0][0], 0]
		dp[1][0] += a[alt[1]]
		for i in range(2, len(alt)):
			dp[i][0] = a[alt[i]]
			if a[alt[i - 1]] + a[alt[i]] < a[alt[i] - 1] and dp[i - 1] > dp[i - 2]:
				dp[i][0] += dp[i - 1][0]
				dp[i][1] = i - 1
			elif i < 3 or dp[i - 2] > dp[i - 3]:
				dp[i][0] += dp[i - 2][0]
				dp[i][1] = i - 2
			else:
				dp[i][0] += dp[i - 3][0]
				dp[i][1] = i - 3
		sub += max(dp[-1][0], dp[-2][0])
		if dp[-1] > dp[-2]:
			pos = len(alt) - 1
		else:
			pos = len(alt) - 2
		while pos != -1:
			swi[alt[pos]] = True
			pos = dp[pos][1]
	for i in range(n):
		if swi[i]:
			a[i] *= -1
	s = ''
	for i in range(len(a) - 1):
		s += str(a[i]) + ' '
	print(*a[:-1])


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	sign = [[0] * n for _ in range(2)]
	pr = [0] * n
	dp = [[0] * n for _ in range(2)]
	if n > 1:
		if arr[0] < arr[1]:
			pr[0] = 1
	for i in range(1, n - 1):
		if arr[i - 1] > arr[i] and arr[i] < arr[i + 1]:
			pr[i] = 1
	if arr[n - 1] < arr[n - 2]:
		pr[n - 1] = 1
	val = 0
	for i in range(n):
		if pr[i] > 0:
			if val == 0:
				val += 1
				dp[0][i] = 0
				dp[1][i] = arr[i]
				sign[1][i] = 2
				sign[0][i] = 6
			elif val == 2:
				val = 1
				max1 = -1
				t = -1
				if dp[0][i - 2] > dp[1][i - 2]:
					max1 = dp[0][i - 2]
					t = 0
				else:
					max1 = dp[1][i - 2]
					t = 1
				if arr[i - 2] + arr[i] >= arr[i - 1]:
					dp[0][i] = max1
					sign[0][i] = t
					dp[1][i] = dp[0][i - 2] + arr[i]
					sign[1][i] = 0
				else:
					dp[0][i] = max1
					sign[0][i] = t
					dp[1][i] = max1 + arr[i]
					sign[1][i] = t
		elif pr[i] == 0:
			if val == 1:
				val = 2
			elif val == 2:
				max1 = -1
				t = -1
				if dp[0][i - 2] > dp[1][i - 2]:
					t = 0
				else:
					t = 1
				sign[1][i] = 3 + t
				sign[0][i] = 3 + t
				val = 0
	start = 0
	if val == 1:
		max1 = -1
		t = -1
		if dp[0][n - 1] > dp[1][n - 1]:
			t = 0
		else:
			t = 1
		start = t
	elif val == 2:
		max1 = -1
		t = -1
		if dp[0][n - 2] > dp[1][n - 2]:
			t = 0
		else:
			t = 1
		start = t
	down = start
	for i in reversed(range(n)):
		if sign[down][i] == 5:
			if pr[i] > 0 and down > 0:
				arr[i] = arr[i] * -1
			down = 1
		elif sign[down][i] == 4:
			if pr[i] > 0 and down > 0:
				arr[i] = arr[i] * -1
			down = 1
		elif sign[down][i] == 3:
			if pr[i] > 0 and down > 0:
				arr[i] = arr[i] * -1
			down = 0
		elif sign[down][i] == 2:
			if pr[i] > 0 and down > 0:
				arr[i] = arr[i] * -1
			down = 1
		elif sign[down][i] == 6:
			down = 1
		elif sign[down][i] == 1:
			if pr[i] > 0 and down > 0:
				arr[i] = arr[i] * -1
			down = 1
		elif sign[down][i] == 0:
			if pr[i] > 0 and down > 0:
				arr[i] = arr[i] * -1
			if pr[i] > 0:
				down = 0
	for num in arr:
		print(num, end=' ')
	print()


t = int(input())
for k in range(t):
	n = int(input())
	l = [int(x) for x in input().split()]
	if l[0] > l[1]:
		l[1] = -l[1]
	if l[0] < l[1]:
		l[0] = -l[0]
	if len(l) > 2:
		for i in range(2, len(l)):
			if l[i] + l[i - 1] <= 0:
				l[i - 1] = -l[i - 1]
			if l[i] < l[i - 1]:
				l[i] = -l[i]
		s = []
		for i in range(len(l) - 2):
			s.append(l[i] + l[i + 1] + l[i + 2])
		i = 0
		while i < len(s):
			if s[i] <= 0:
				j = i
				while j < len(s):
					if s[j] <= 0:
						j = j + 2
						continue
					if s[j] > 0:
						j = j - 2
						break
				if j >= len(s):
					j = j - 2
				s1 = 0
				s2 = 0
				x = j + 2
				p = i
				s1 = l[p]
				s2 = l[p + 2]
				s1l = [p]
				s2l = [p + 2]
				p = p + 4
				while p <= x:
					if s1 > s2:
						s1 = s1 + l[p]
						s1l = s1l + [p]
					else:
						s1 = s2 + l[p]
						s1l = s2l + [p]
					if p + 2 <= x:
						if s2 < s1:
							s2 = s1 + l[p + 2]
							s2l = s1l + [p + 2]
						else:
							s2 = s2 + l[p + 2]
							s2l = s2l + [p + 2]
					p = p + 4
				if s1 > s2:
					p = i
					for j in range(len(s1l)):
						l[s1l[j]] = -l[s1l[j]]
				else:
					for j in range(len(s2l)):
						l[s2l[j]] = -l[s2l[j]]
				i = x + 1
			else:
				i = i + 1
	for i in range(len(l)):
		print(l[i], end=' ')
	print('')


tc = int(input())
while tc > 0:
	n = int(input())
	array = list(map(int, input().split()))
	ans = [0] * n
	if n == 2:
		if array[0] < array[1]:
			ans[0] = -array[0]
			ans[1] = array[1]
		elif array[0] == array[1]:
			ans[0] = array[0]
			ans[1] = array[1]
		else:
			ans[0] = array[0]
			ans[1] = -array[1]
		for i in ans:
			print(i, end=' ')
		print()
		tc -= 1
		continue
	inf = 10 ** 14 + 1
	dp = [[inf, inf] for i in range(n)]
	parent = [[-1, -1] for i in range(n)]
	dp[0][0] = array[0]
	dp[0][1] = -array[0]
	if array[0] >= array[1]:
		dp[0][1] = inf
	dp[1][0] = min(dp[0][0], dp[0][1]) + array[1]
	if dp[0][0] < dp[0][1]:
		parent[1][0] = 0
	else:
		parent[1][0] = 1
	dp[1][1] = dp[0][0] - array[1]
	parent[1][1] = 0
	if array[1] >= array[0] or (n >= 3 and array[1] >= array[2] or n == 2):
		dp[1][1] = inf
	for i in range(2, n):
		dp[i][0] = min(array[i] + dp[i - 1][0], array[i] + dp[i - 1][1])
		if dp[i - 1][0] < dp[i - 1][1]:
			parent[i][0] = 0
		else:
			parent[i][0] = 1
		check = True
		check = check and array[i] < array[i - 1]
		next = inf
		prev = array[i - 1]
		if i < n - 1:
			next = array[i + 1]
		check = check and array[i] < next
		if not check:
			continue
		pprev = array[i - 2]
		opt1 = inf
		if prev - pprev - array[i] > 0:
			opt1 = dp[i - 2][1] + array[i - 1] - array[i]
		opt2 = dp[i - 2][0] + array[i - 1] - array[i]
		dp[i][1] = min(opt1, opt2)
		if opt1 < opt2:
			parent[i][1] = 1
		else:
			parent[i][1] = 0
	s = -100
	if dp[n - 1][0] < dp[n - 1][1]:
		s = 0
	else:
		s = 1
	ind = n - 1
	while ind >= 0:
		cur = array[ind]
		if s == 1:
			cur *= -1
		ans[ind] = cur
		if ind == 0:
			break
		temp = parent[ind][s]
		if s == 1:
			ans[ind - 1] = array[ind - 1]
			ind -= 1
		s = temp
		ind -= 1
	for i in ans:
		print(i, end=' ')
	print()
	tc -= 1


T = int(input())
for t in range(T):
	N = int(input())
	inp = input().split()
	A = [int(i) for i in inp]
	if N == 1:
		print(-A[0])
		continue
	if A[0] < A[1]:
		A[0] = -A[0]
	if A[N - 1] < A[N - 2]:
		A[N - 1] = -A[N - 1]
	for i in range(1, N - 1):
		b = A[i]
		if b < A[i - 1] and b < A[i + 1]:
			A[i] = -A[i]
	subs = []
	start = 0
	end = 0
	while start < N - 2:
		if A[start] > 0:
			start += 1
			continue
		if start == N - 4 or start == N - 3:
			if A[start] + A[start + 1] + A[start + 2] <= 0:
				subs.append((start, start + 2))
			break
		for i in range(start + 2, N, 2):
			if A[i] > 0 or A[i - 2] + A[i - 1] + A[i] > 0:
				break
		if i == N - 1 or i == N - 2:
			if A[i] < 0 and A[i - 2] + A[i - 1] + A[i] <= 0:
				subs.append((start, i))
			else:
				subs.append((start, i - 2))
		elif i > start + 2:
			subs.append((start, i - 2))
		start = i
	for s in subs:
		start = s[0]
		end = s[1]
		if end - start == 2:
			if A[start] > A[end]:
				A[start] = -A[start]
			else:
				A[end] = -A[end]
		else:
			fa = [start]
			sa = [start + 2]
			ta = [start, start + 4]
			fs = A[start]
			ss = A[start + 2]
			ts = A[start] + A[start + 4]
			for i in range(start + 6, end + 1, 2):
				if ss <= fs:
					temps = ss + A[i]
					tempa = sa + [i]
				else:
					temps = fs + A[i]
					tempa = fa + [i]
				fa = sa
				sa = ta
				fs = ss
				ss = ts
				ta = tempa
				ts = temps
			if ts <= ss:
				tempa = ta
			else:
				tempa = sa
			for i in range(start, end + 1, 2):
				A[i] = -A[i]
			for i in tempa:
				A[i] = -A[i]
	a = ''
	for i in range(N - 1):
		a += str(A[i]) + ' '
	print(a + str(A[-1]))


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	all = []
	totka = -1
	flag = False
	z = -1
	for j in range(n):
		if j == 0:
			if a[j + 1] > a[j]:
				totka = j
				continue
			continue
		if j == n - 1:
			if a[j - 1] > a[j]:
				if totka == -1:
					totka = j
				else:
					if j - totka == 2 and a[j] + a[totka] >= a[j - 1]:
						if flag == False:
							flag = True
							z = totka
					else:
						if flag == True:
							all.append((z, totka))
						else:
							a[totka] *= -1
						z = -1
						flag = False
					totka = j
			continue
		if a[j - 1] > a[j] and a[j + 1] > a[j]:
			if totka == -1:
				totka = j
			else:
				if j - totka == 2 and a[j] + a[totka] >= a[j - 1]:
					if flag == False:
						flag = True
						z = totka
				else:
					if flag == True:
						all.append((z, totka))
					else:
						a[totka] *= -1
					z = -1
					flag = False
				totka = j
			continue
	if flag == True:
		all.append((z, totka))
	elif a[totka] < a[totka - 1]:
		a[totka] *= -1
	for j in range(len(all)):
		cc = 0
		ss = 0
		xy = 1
		vv = 0
		sum = []
		for k in range(all[j][0], all[j][1] + 1, 2):
			if cc == 0:
				sum.append(a[k])
				cc += 1
				continue
			if cc == 1:
				sum.append(max(sum[0], a[k]))
				cc += 1
				continue
			sum.append(max(sum[cc - 2] + a[k], sum[cc - 1]))
			cc += 1
		rr = []
		cc = len(sum) - 1
		k = all[j][1]
		while k >= all[j][0] - 1:
			if cc < 0:
				break
			if cc >= 2:
				if sum[cc] == sum[cc - 2] + a[k]:
					rr.append(cc)
					k -= 2
					cc -= 2
				else:
					cc -= 1
			elif cc == 1:
				if sum[cc] == a[k]:
					rr.append(cc)
					cc = -1
				else:
					cc = 0
			else:
				rr.append(cc)
				cc -= 1
			k -= 2
		for k in range(len(rr)):
			a[all[j][0] + rr[k] * 2] *= -1
	for j in range(n):
		print(a[j], end=' ')
	print()


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	sothik = False
	baash = -1
	index = []
	starting = -1
	for gh in range(n):
		if gh == 0:
			if a[gh + 1] > a[gh]:
				baash = gh
				continue
			continue
		if gh == n - 1:
			if a[gh - 1] > a[gh]:
				if baash == -1:
					baash = gh
				else:
					if gh - baash == 2 and a[gh] + a[baash] >= a[gh - 1]:
						if sothik == False:
							sothik = True
							starting = baash
					else:
						if sothik == True:
							index.append((starting, baash))
						else:
							a[baash] *= -1
						starting = -1
						sothik = False
					baash = gh
			continue
		if a[gh - 1] > a[gh] and a[gh + 1] > a[gh]:
			if baash == -1:
				baash = gh
			else:
				if gh - baash == 2 and a[gh] + a[baash] >= a[gh - 1]:
					if sothik == False:
						sothik = True
						starting = baash
				else:
					if sothik == True:
						index.append((starting, baash))
					else:
						a[baash] *= -1
					starting = -1
					sothik = False
				baash = gh
			continue
	if sothik == True:
		index.append((starting, baash))
	elif a[baash] < a[baash - 1]:
		a[baash] *= -1
	for gh in range(len(index)):
		dp = []
		counter = 0
		for kk in range(index[gh][0], index[gh][1] + 1, 2):
			if counter == 0:
				dp.append(a[kk])
				counter += 1
				continue
			if counter == 1:
				dp.append(max(dp[0], a[kk]))
				counter += 1
				continue
			dp.append(max(dp[counter - 2] + a[kk], dp[counter - 1]))
			counter += 1
		counter = len(dp) - 1
		kk = index[gh][1]
		while kk >= index[gh][0]:
			if counter < 0:
				break
			if counter >= 2:
				if dp[counter] == dp[counter - 2] + a[kk]:
					a[index[gh][0] + counter * 2] *= -1
					kk -= 2
					counter -= 2
				else:
					counter -= 1
			elif counter == 1:
				if dp[counter] == a[kk]:
					a[index[gh][0] + counter * 2] *= -1
					counter = -1
				else:
					counter = 0
			else:
				a[index[gh][0] + counter * 2] *= -1
				counter -= 1
			kk -= 2
	print(*a)


def rslv(st, sp):
	arr = A[st:sp + 1:2]
	su = [0, 0]
	ind = [0, 0]
	(su[0], ind[0]) = (arr[0], [st])
	(su[1], ind[1]) = (su[0], [st]) if su[0] >= arr[1] else (arr[1], [st + 2])
	for k in range(2, len(arr)):
		if su[0] + arr[k] > su[1]:
			(su[1], ind[1], su[0], ind[0]) = (su[0] + arr[k], ind[0] + [st + 2 * k], su[1], ind[1])
		else:
			(su[0], ind[0]) = (su[1], ind[1])
	for k in ind[1]:
		A[k] *= -1
T = int(input())
for test_case in range(T):
	N = int(input())
	A = [10000000000.0, 10000000000.0] + list(map(int, input().split())) + [10000000000.0]
	i = 2
	while i < N + 2:
		if A[i - 1] > A[i] < A[i + 1]:
			if A[i - 1] + A[i - 2] - A[i] > 0:
				A[i] *= -1
			else:
				A[i - 2] *= -1
				sti = i - 2
				stp = i
				for j in range(i + 2, N + 2, 2):
					if A[j - 1] > A[j] < A[j + 1] and A[j - 1] - A[j - 2] - A[j] < 1:
						stp += 2
					else:
						break
				rslv(sti, stp)
				i = stp
			i += 1
		i += 1
	print(*A[2:N + 2])


def fix_negatives(seq, start, end):
	seq[start] *= -1
	excl = (0, ())
	incl = (seq[start], (start,))
	for i in range(start + 2, end + 1, 2):
		seq[i] *= -1
		tmp = incl
		if excl[0] + seq[i] > incl[0]:
			incl = (excl[0] + seq[i], excl[1] + (i,))
		excl = tmp
	for i in incl[1]:
		seq[i] *= -1

def init_negatives(seq):
	for i in range(len(seq)):
		if i == 0:
			if seq[0] < seq[1]:
				seq[0] *= -1
		elif i == len(seq) - 1:
			if seq[i] < seq[i - 1]:
				seq[i] *= -1
		elif seq[i] < seq[i - 1] and seq[i] < seq[i + 1]:
			seq[i] *= -1

def solve(seq):
	init_negatives(seq)
	i = 0
	while i < len(seq):
		start = end = i
		while i < len(seq) - 2 and seq[i] + seq[i + 1] + seq[i + 2] <= 0:
			end = i + 2
			i = i + 2
		if start != end:
			fix_negatives(seq, start, end)
		i = i + 1
	return seq

def main():
	import sys
	sys.setrecursionlimit(1000000)
	test_cases = int(sys.stdin.readline())
	for _ in range(test_cases):
		seq_len = int(sys.stdin.readline())
		seq = [int(i) for i in sys.stdin.readline().split()]
		print(' '.join((str(i) for i in solve(seq))))
main()


from pprint import pprint
from time import time

def get_input():
	ip = input().split()
	ip = [int(i) for i in ip]
	if len(ip) == 1:
		return ip[0]
	return ip

def get_min_sum(A, i, memo):
	la = len(A) - i
	if la <= 2:
		return [sum(A[-la:]), A[:]]
	if (la, A[i], A[i + 1], A[i + 2]) in memo:
		return memo[la, A[i], A[i + 1], A[i + 2]]
	if sum(A[i:i + 3]) > 0:
		(sa1, A1) = get_min_sum(A, i + 1, memo)
		memo[la, A[i], A[i + 1], A[i + 2]] = [A[i] + sa1, A[i:i + 4]]
		return memo[la, A[i], A[i + 1], A[i + 2]]
	else:
		a0 = A[i]
		a2 = A[i + 2]
		A[i] = abs(a0)
		(sb, B1) = get_min_sum(A, i + 1, memo)
		(sb, B1) = (A[i] + sb, A[i:i + 4])
		A[i] = a0
		A[i + 2] = abs(a2)
		(sc, C1) = get_min_sum(A, i + 1, memo)
		(sc, C1) = (A[i] + sc, A[i:i + 4])
		A[i + 2] = a2
		if sb <= sc and sum(B1[:3]) > 0:
			memo[la, A[i], A[i + 1], A[i + 2]] = (sb, B1)
			return (sb, B1)
		elif sum(C1[:3]) > 0:
			memo[la, A[i], A[i + 1], A[i + 2]] = (sc, C1)
			return (sc, C1)
		else:
			a0 = A[i]
			a2 = A[i + 2]
			A[i] = abs(a0)
			A[i + 2] = abs(a2)
			(sd, D1) = get_min_sum(A, i + 1, memo)
			(sd, D1) = (A[i] + sd, A[i:i + 4])
			A[i] = a0
			A[i + 2] = a2
			memo[la, A[i], A[i + 1], A[i + 2]] = (sd, D1)
			return (sd, D1)

def main():
	N = get_input()
	A = get_input()
	N = len(A)
	if A[0] < A[1]:
		A[0] = A[0] * -1
	if A[-1] < A[-2]:
		A[-1] = A[-1] * -1
	for i in range(1, len(A) - 1):
		if abs(A[i]) < abs(A[i + 1]) and abs(A[i]) < abs(A[i - 1]):
			A[i] = A[i] * -1
	memo = {}
	for i in range(len(A) - 3, -1, -1):
		get_min_sum(A, i, memo)
	if N < 3:
		(_, B) = get_min_sum(A, 0, memo)
	else:
		B = []
		(_, T) = memo[N, A[0], A[1], A[2]]
		i = N
		while len(T) > 3:
			B.append(T[0])
			i = i - 1
			(_, T) = memo[i, T[1], T[2], T[3]]
		B = B + T
	for b in B[:-1]:
		print(b, end=' ')
	print(B[-1])
tests = int(input())
for _ in range(tests):
	main()