#include <bits/stdc++.h>
using namespace std;
const int nax = 1e6 + 5;
const int inf = 1e9;
int a[nax];
int n;
map<tuple<int, int, int>, pair<pair<int, int>, int> > pop;
set<pair<int, int> > alive;
set<pair<int, int> > nxt;
void go(int id, int val) {
  for (pair<int, int> was : alive) {
    if (val < was.first && val < was.second) continue;
    if (val < was.first) {
      nxt.insert(make_pair(was.first, val));
      pop[make_tuple(id, was.first, val)] = make_pair(was, val);
    } else {
      nxt.insert(make_pair(val, was.second));
      pop[make_tuple(id, val, was.second)] = make_pair(was, val);
    }
  }
}
void solve() {
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> a[i];
  pop.clear();
  alive.clear();
  nxt.clear();
  alive.insert(make_pair(-a[1], -inf));
  pop[make_tuple(1, -a[1], -inf)] = make_pair(make_pair(0, 0), -a[1]);
  for (int i = 2; i <= n; i++) {
    int val = a[i];
    nxt.clear();
    go(i, val);
    go(i, -val);
    while (1) {
      vector<pair<int, int> > out;
      for (pair<int, int> cur : nxt) {
        bool ex = false;
        for (pair<int, int> dom : nxt) {
          if (dom.first < cur.first && dom.second < cur.second) ex = true;
          if (dom.first == cur.first && dom.second < cur.second) ex = true;
          if (dom.first < cur.first && dom.second == cur.second) ex = true;
        }
        if (ex) out.push_back(cur);
      }
      if (out.empty()) break;
      for (pair<int, int> cur : out) nxt.erase(cur);
    }
    alive = nxt;
  }
  if (alive.empty()) {
    cout << "NO"
         << "\n";
  } else {
    cout << "YES"
         << "\n";
    vector<int> ans;
    int id = n;
    pair<int, int> cur = (*alive.begin());
    while (id >= 1) {
      auto go = pop[make_tuple(id, cur.first, cur.second)];
      ans.push_back(go.second);
      cur = go.first;
      id -= 1;
    }
    reverse(ans.begin(), ans.end());
    for (int x : ans) cout << x << " ";
    cout << "\n";
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int tt = 1;
  cin >> tt;
  while (tt--) solve();
  return 0;
}

### Prompt

In cpp, your task is to solve the following problem:

You are given a permutation p consisting of n integers 1, 2, ..., n (a permutation is an array where each element from 1 to n occurs exactly once).

Let's call an array a bipartite if the following undirected graph is bipartite:

  * the graph consists of n vertices; 
  * two vertices i and j are connected by an edge if i < j and a_i > a_j. 



Your task is to find a bipartite array of integers a of size n, such that a_i = p_i or a_i = -p_i, or report that no such array exists. If there are multiple answers, print any of them.

Input

The first line contains a single integer t (1 ≤ t ≤ 2 ⋅ 10^5) — the number of test cases.

The first line of each test case contains a single integer n (1 ≤ n ≤ 10^6) — the size of the permutation.

The second line contains n integers p_1, p_2, ..., p_n.

The sum of n over all test cases doesn't exceed 10^6.

Output

For each test case, print the answer in the following format. If such an array a does not exist, print "NO" in a single line. Otherwise, print "YES" in the first line and n integers — array a in the second line.

Example

Input


4
3
1 2 3
6
1 3 2 6 5 4
4
4 1 3 2
8
3 2 1 6 7 8 5 4


Output


YES
1 2 3
NO
YES
-4 -1 -3 -2
YES
-3 -2 1 6 7 -8 -5 -4

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const int nax = 1e6 + 5;
const int inf = 1e9;
int a[nax];
int n;
map<tuple<int, int, int>, pair<pair<int, int>, int> > pop;
set<pair<int, int> > alive;
set<pair<int, int> > nxt;
void go(int id, int val) {
  for (pair<int, int> was : alive) {
    if (val < was.first && val < was.second) continue;
    if (val < was.first) {
      nxt.insert(make_pair(was.first, val));
      pop[make_tuple(id, was.first, val)] = make_pair(was, val);
    } else {
      nxt.insert(make_pair(val, was.second));
      pop[make_tuple(id, val, was.second)] = make_pair(was, val);
    }
  }
}
void solve() {
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> a[i];
  pop.clear();
  alive.clear();
  nxt.clear();
  alive.insert(make_pair(-a[1], -inf));
  pop[make_tuple(1, -a[1], -inf)] = make_pair(make_pair(0, 0), -a[1]);
  for (int i = 2; i <= n; i++) {
    int val = a[i];
    nxt.clear();
    go(i, val);
    go(i, -val);
    while (1) {
      vector<pair<int, int> > out;
      for (pair<int, int> cur : nxt) {
        bool ex = false;
        for (pair<int, int> dom : nxt) {
          if (dom.first < cur.first && dom.second < cur.second) ex = true;
          if (dom.first == cur.first && dom.second < cur.second) ex = true;
          if (dom.first < cur.first && dom.second == cur.second) ex = true;
        }
        if (ex) out.push_back(cur);
      }
      if (out.empty()) break;
      for (pair<int, int> cur : out) nxt.erase(cur);
    }
    alive = nxt;
  }
  if (alive.empty()) {
    cout << "NO"
         << "\n";
  } else {
    cout << "YES"
         << "\n";
    vector<int> ans;
    int id = n;
    pair<int, int> cur = (*alive.begin());
    while (id >= 1) {
      auto go = pop[make_tuple(id, cur.first, cur.second)];
      ans.push_back(go.second);
      cur = go.first;
      id -= 1;
    }
    reverse(ans.begin(), ans.end());
    for (int x : ans) cout << x << " ";
    cout << "\n";
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int tt = 1;
  cin >> tt;
  while (tt--) solve();
  return 0;
}

```