// WA
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <iostream>
#include <tuple>
#include <iomanip>
#include <string>
#include <ctime>
#include <cassert>
#include <queue>

using namespace std;

using ll = long long;
using pli = pair<ll, int>;

const int MAX_N = int(1e5);
const ll MAX_A = ll(1e9);

void solve() {
  int N; assert(cin >> N); assert(2 <= N && N <= MAX_N);
  N += 2;
  vector<ll> A(N, 1e10); 
  for(int i = 1; i+1 < N; i++) {
    cin >> A[i];
    assert(1 <= A[i] && A[i] <= MAX_A);
  }

  vector<int> R(N);
  for(int d = 0; d < 2; d++) {
    for(int i = d, j = d; i < N; i += 2) {
      if(j < i) j = i;
      while(j+2 < N && A[j] - A[j+1] > 0 && A[j+2] - A[j+1] > 0 && (i == j || - A[j-1] + A[j] - A[j+1] > 0)) j += 2;
      R[i] = j;
    }
  }

  vector<ll> S[2];
  for(int d = 0; d < 2; d++) {
    for(int i = 0; i < N; i++) S[d].push_back(((d + i) % 2 == 0 ? 1 : -1) * A[i] + (S[d].empty() ? 0 : S[d].back()));
  }
  
  priority_queue<pli, vector<pli>, greater<pli>> pq[2];
  vector<ll> tb(N, ll(2e18));
  vector<int> rev(N, -1);
  tb[0] = A[0];
  pq[0].emplace(0, 0);
  for(int i = 1; i < N; i++) {
    int d = i % 2;
    tb[i] = tb[i-1] + A[i];
    rev[i] = i;
    while(!pq[d].empty()) {
      ll v; int j; tie(v, j) = pq[d].top(); 
      if(i <= R[j]) {
        if(tb[i] > S[d][i] + v) {
          tb[i] = S[d][i] + v;
          rev[i] = j;
        }
        break;
      }
      pq[d].pop();
    }
    pq[d].emplace(tb[i-1] - S[d][i-1], i);
  }
  
  vector<ll> B = A;
  for(int i = N-1; i >= 0; i = rev[i] - 1) {
    for(int j = i-1; j > rev[i]; j -= 2) B[j] *= -1;
  }

  for(int i = 1; i+1 < N; i++) {
    cout << B[i] << (i+1 == N-1 ? "\n" : " ");
  }
}

int main() {
#ifdef IN_MY_COMPUTER
  freopen("chsign.in", "r", stdin);
#else
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
#endif

  int T; cin >> T;
  while(T--) {
    solve();
  }
  return 0;
}