#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target( \
    "fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")
using namespace std;
const double eps = 1e-6;
struct inout {
  static const int ibufl = 1 << 25;
  char in_buf[ibufl + 5], out_buf[ibufl + 5], *inf, *ouf;
  void init() {
    fread(in_buf, 1, ibufl, stdin);
    inf = in_buf;
    ouf = out_buf;
  }
  inout& operator>>(int& a) {
    int fh = 1;
    while (!(isdigit(*inf) || *inf == '-')) ++inf;
    if (*inf == '-') fh = -1, ++inf;
    a = 0;
    while (isdigit(*inf)) {
      a = a * 10 + *inf - '0';
      ++inf;
    }
    a *= fh;
    return *this;
  }
  inout& operator>>(char& a) {
    while (*inf == ' ' || *inf == '\n') ++inf;
    a = *inf;
    ++inf;
    return *this;
  }
  inout& operator>>(char* a) {
    while (*inf == ' ' || *inf == '\n') ++inf;
    while (!(*inf == ' ' || *inf == '\n')) {
      *a = *inf;
      ++inf;
      ++a;
    }
    *a = '\0';
    return *this;
  }
  inout& operator>>(double& a) {
    int fh = 1;
    double s;
    while (!(isdigit(*inf) || *inf == '-')) ++inf;
    if (*inf == '-') fh = -1, ++inf;
    a = 0;
    while (isdigit(*inf)) {
      a = a * 10 + *inf - '0';
      ++inf;
    }
    if (*inf == '.') {
      s = 0.1;
      ++inf;
      while (isdigit(*inf)) {
        a += s * (*inf - '0');
        ++inf;
        s *= 0.1;
      }
    }
    a *= fh;
    return *this;
  }
  void writeint(int x) {
    if (x / 10) writeint(x / 10);
    *ouf = x % 10 + '0';
    ++ouf;
  }
  inout& operator<<(int a) {
    if (a < 0) {
      *ouf = '-';
      ++ouf;
      a = -a;
    }
    writeint(a);
    return *this;
  }
  static const int sz = 2;
  inout& operator<<(char a) {
    *ouf = a;
    ++ouf;
    return *this;
  }
  inout& operator<<(char* a) {
    while (*a) {
      *ouf = *a;
      ++ouf;
      ++a;
    }
    return *this;
  }
  inout& operator<<(double a) {
    if (a < -eps) {
      *ouf = '-';
      ++ouf;
      a = -a;
    }
    writeint((int)a);
    a -= (int)a;
    *ouf = '.';
    ++ouf;
    for (int i = 1; i <= sz; i++) {
      a = a * 10;
      *ouf = (int)a + '0';
      ++ouf;
      a -= (int)a;
    }
    return *this;
  }
  void out() { fwrite(out_buf, 1, ouf - out_buf, stdout); }
};
inout io;
int a[1000005], lst[1000005][2], dp[1000005][2];
void solve() {
  int n;
  io >> n;
  for (int i = 1; i <= n; i++) io >> a[i];
  a[0] = 1e9;
  dp[0][0] = dp[0][1] = -1e9;
  for (int i = 1; i <= n; i++) {
    dp[i][0] = dp[i][1] = 1e9;
    for (int j = 0; j < 2; j++) {
      int k = j ? (-a[i]) : a[i];
      if (k > a[i - 1]) {
        dp[i][j] = dp[i - 1][0];
        lst[i][j] = 0;
      }
      if (k > dp[i - 1][1] && dp[i][j] > -a[i - 1]) {
        dp[i][j] = -a[i - 1];
        lst[i][j] = 1;
      }
      if (k > dp[i - 1][0] && dp[i][j] > a[i - 1]) {
        dp[i][j] = a[i - 1];
        lst[i][j] = 0;
      }
      if (k > -a[i - 1] && dp[i - 1][1] < dp[i][j]) {
        dp[i][j] = dp[i - 1][1];
        lst[i][j] = 1;
      }
    }
  }
  if (dp[n][0] > n && dp[n][1] > n) {
    io << "NO\n";
    return;
  }
  int now = 0;
  if (dp[n][now] > n) now = 1;
  for (int i = n; i >= 1; i--) {
    if (now) a[i] = -a[i];
    now = lst[i][now];
  }
  io << "YES\n";
  for (int i = 1; i <= n; i++) io << a[i] << ' ';
  io << '\n';
}
signed main() {
  io.init();
  int T;
  io >> T;
  while (T--) solve();
  io.out();
  return 0;
}

### Prompt

Please formulate a Cpp solution to 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>
#pragma GCC optimize("Ofast")
#pragma GCC target( \
    "fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")
using namespace std;
const double eps = 1e-6;
struct inout {
  static const int ibufl = 1 << 25;
  char in_buf[ibufl + 5], out_buf[ibufl + 5], *inf, *ouf;
  void init() {
    fread(in_buf, 1, ibufl, stdin);
    inf = in_buf;
    ouf = out_buf;
  }
  inout& operator>>(int& a) {
    int fh = 1;
    while (!(isdigit(*inf) || *inf == '-')) ++inf;
    if (*inf == '-') fh = -1, ++inf;
    a = 0;
    while (isdigit(*inf)) {
      a = a * 10 + *inf - '0';
      ++inf;
    }
    a *= fh;
    return *this;
  }
  inout& operator>>(char& a) {
    while (*inf == ' ' || *inf == '\n') ++inf;
    a = *inf;
    ++inf;
    return *this;
  }
  inout& operator>>(char* a) {
    while (*inf == ' ' || *inf == '\n') ++inf;
    while (!(*inf == ' ' || *inf == '\n')) {
      *a = *inf;
      ++inf;
      ++a;
    }
    *a = '\0';
    return *this;
  }
  inout& operator>>(double& a) {
    int fh = 1;
    double s;
    while (!(isdigit(*inf) || *inf == '-')) ++inf;
    if (*inf == '-') fh = -1, ++inf;
    a = 0;
    while (isdigit(*inf)) {
      a = a * 10 + *inf - '0';
      ++inf;
    }
    if (*inf == '.') {
      s = 0.1;
      ++inf;
      while (isdigit(*inf)) {
        a += s * (*inf - '0');
        ++inf;
        s *= 0.1;
      }
    }
    a *= fh;
    return *this;
  }
  void writeint(int x) {
    if (x / 10) writeint(x / 10);
    *ouf = x % 10 + '0';
    ++ouf;
  }
  inout& operator<<(int a) {
    if (a < 0) {
      *ouf = '-';
      ++ouf;
      a = -a;
    }
    writeint(a);
    return *this;
  }
  static const int sz = 2;
  inout& operator<<(char a) {
    *ouf = a;
    ++ouf;
    return *this;
  }
  inout& operator<<(char* a) {
    while (*a) {
      *ouf = *a;
      ++ouf;
      ++a;
    }
    return *this;
  }
  inout& operator<<(double a) {
    if (a < -eps) {
      *ouf = '-';
      ++ouf;
      a = -a;
    }
    writeint((int)a);
    a -= (int)a;
    *ouf = '.';
    ++ouf;
    for (int i = 1; i <= sz; i++) {
      a = a * 10;
      *ouf = (int)a + '0';
      ++ouf;
      a -= (int)a;
    }
    return *this;
  }
  void out() { fwrite(out_buf, 1, ouf - out_buf, stdout); }
};
inout io;
int a[1000005], lst[1000005][2], dp[1000005][2];
void solve() {
  int n;
  io >> n;
  for (int i = 1; i <= n; i++) io >> a[i];
  a[0] = 1e9;
  dp[0][0] = dp[0][1] = -1e9;
  for (int i = 1; i <= n; i++) {
    dp[i][0] = dp[i][1] = 1e9;
    for (int j = 0; j < 2; j++) {
      int k = j ? (-a[i]) : a[i];
      if (k > a[i - 1]) {
        dp[i][j] = dp[i - 1][0];
        lst[i][j] = 0;
      }
      if (k > dp[i - 1][1] && dp[i][j] > -a[i - 1]) {
        dp[i][j] = -a[i - 1];
        lst[i][j] = 1;
      }
      if (k > dp[i - 1][0] && dp[i][j] > a[i - 1]) {
        dp[i][j] = a[i - 1];
        lst[i][j] = 0;
      }
      if (k > -a[i - 1] && dp[i - 1][1] < dp[i][j]) {
        dp[i][j] = dp[i - 1][1];
        lst[i][j] = 1;
      }
    }
  }
  if (dp[n][0] > n && dp[n][1] > n) {
    io << "NO\n";
    return;
  }
  int now = 0;
  if (dp[n][now] > n) now = 1;
  for (int i = n; i >= 1; i--) {
    if (now) a[i] = -a[i];
    now = lst[i][now];
  }
  io << "YES\n";
  for (int i = 1; i <= n; i++) io << a[i] << ' ';
  io << '\n';
}
signed main() {
  io.init();
  int T;
  io >> T;
  while (T--) solve();
  io.out();
  return 0;
}

```