#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using i32 = int;
const int INF = 0x3f3f3f3f;
const double tol = 1e-8;
const int P = 998244353;
int pop_count(i64 x) { return __builtin_popcountll(x); }
int pop_count(int x) { return __builtin_popcount(x); }
template <typename S, typename T>
bool check_and_save_min_in_lhs(S& lhs, const T& rhs) {
  return lhs < rhs ? 1 : lhs = rhs, 0;
}
template <typename S, typename T>
bool check_and_save_max_in_lhs(S& lhs, const T& rhs) {
  return lhs > rhs ? 1 : lhs = rhs, 0;
}
template <typename T>
T min_all(T ele) {
  return ele;
}
template <typename T, typename... Args>
T min_all(T fst_el, Args... others) {
  return min_all(fst_el, mins(others...));
}
template <typename T>
T maxs(T ele) {
  return ele;
}
template <typename T, typename... Args>
T maxs(T fst_el, Args... others) {
  return max(fst_el, maxs(others...));
}
template <typename T>
void read_int(T& num) {
  bool positive = true;
  char ch;
  num = 0;
  while (isspace(ch = getchar()))
    ;
  if (ch == '-')
    positive = false;
  else
    num = ch - '0';
  while ((ch = getchar()) >= '0' && ch <= '9') num = num * 10 + ch - '0';
  if (!positive) num = -num;
}
void read_ints(){};
template <typename T, typename... Args>
void read_ints(T& fst_el, Args&... others) {
  read_int(fst_el);
  read_ints(others...);
}
template <typename T>
void int_out(T num) {
  if (num < 0) {
    putchar('-');
    num = -num;
  }
  if (num > 9) int_out(num / 10);
  putchar(num % 10 + '0');
}
void int_outs() { puts(""); }
template <typename T, typename... Args>
void int_outs(T fst_ele, Args... others) {
  int_out(fst_ele);
  putchar(' ');
  int_outs(others...);
}
const int N = 1000005;
int p[N], dp[N][2][2], pre[N][2][2][2];
int main() {
  int t;
  read_int(t);
  while (t--) {
    int n;
    read_int(n);
    for (int i = 1; i <= n; ++i) {
      read_int(p[i]);
    }
    memset(dp, 0x3f, (n + 2) * sizeof(dp[0]));
    dp[1][0][0] = -n - 1;
    dp[1][0][1] = -n - 1;
    for (int i = 1; i <= n - 1; ++i) {
      for (int cur_pos = 0; cur_pos <= 1; ++cur_pos) {
        for (int cur_sign = 0; cur_sign <= 1; ++cur_sign) {
          if (dp[i][cur_pos][cur_sign] > n) continue;
          int x = p[i] * (cur_sign * 2 - 1);
          int y = dp[i][cur_pos][cur_sign];
          if (cur_pos) swap(x, y);
          for (int next_sign = 0; next_sign <= 1; ++next_sign) {
            int z = next_sign == 0 ? -p[i + 1] : p[i + 1];
            if (z > x) {
              if (y < dp[i + 1][0][next_sign]) {
                pre[i + 1][0][next_sign][0] = cur_pos;
                pre[i + 1][0][next_sign][1] = cur_sign;
                dp[i + 1][0][next_sign] = y;
              }
            } else if (z > y) {
              if (x < dp[i + 1][1][next_sign]) {
                pre[i + 1][1][next_sign][0] = cur_pos;
                pre[i + 1][1][next_sign][1] = cur_sign;
                dp[i + 1][1][next_sign] = x;
              }
            }
          }
        }
      }
    }
    int cur_pos = -1, cur_sign = -1;
    for (int i = 0; i <= 1; ++i) {
      for (int j = 0; j <= 1; ++j) {
        if (dp[n][i][j] <= n) {
          cur_pos = i;
          cur_sign = j;
          break;
        }
      }
    }
    if (cur_pos == -1) {
      puts("NO");
      continue;
    }
    puts("YES");
    for (int i = n; i >= 1; --i) {
      if (cur_sign == 0) p[i] = -p[i];
      int tpos = cur_pos;
      cur_pos = pre[i][tpos][cur_sign][0];
      cur_sign = pre[i][tpos][cur_sign][1];
    }
    for (int i = 1; i <= n; ++i) {
      printf("%d ", p[i]);
    }
    puts("");
  }
  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;
using i64 = long long;
using i32 = int;
const int INF = 0x3f3f3f3f;
const double tol = 1e-8;
const int P = 998244353;
int pop_count(i64 x) { return __builtin_popcountll(x); }
int pop_count(int x) { return __builtin_popcount(x); }
template <typename S, typename T>
bool check_and_save_min_in_lhs(S& lhs, const T& rhs) {
  return lhs < rhs ? 1 : lhs = rhs, 0;
}
template <typename S, typename T>
bool check_and_save_max_in_lhs(S& lhs, const T& rhs) {
  return lhs > rhs ? 1 : lhs = rhs, 0;
}
template <typename T>
T min_all(T ele) {
  return ele;
}
template <typename T, typename... Args>
T min_all(T fst_el, Args... others) {
  return min_all(fst_el, mins(others...));
}
template <typename T>
T maxs(T ele) {
  return ele;
}
template <typename T, typename... Args>
T maxs(T fst_el, Args... others) {
  return max(fst_el, maxs(others...));
}
template <typename T>
void read_int(T& num) {
  bool positive = true;
  char ch;
  num = 0;
  while (isspace(ch = getchar()))
    ;
  if (ch == '-')
    positive = false;
  else
    num = ch - '0';
  while ((ch = getchar()) >= '0' && ch <= '9') num = num * 10 + ch - '0';
  if (!positive) num = -num;
}
void read_ints(){};
template <typename T, typename... Args>
void read_ints(T& fst_el, Args&... others) {
  read_int(fst_el);
  read_ints(others...);
}
template <typename T>
void int_out(T num) {
  if (num < 0) {
    putchar('-');
    num = -num;
  }
  if (num > 9) int_out(num / 10);
  putchar(num % 10 + '0');
}
void int_outs() { puts(""); }
template <typename T, typename... Args>
void int_outs(T fst_ele, Args... others) {
  int_out(fst_ele);
  putchar(' ');
  int_outs(others...);
}
const int N = 1000005;
int p[N], dp[N][2][2], pre[N][2][2][2];
int main() {
  int t;
  read_int(t);
  while (t--) {
    int n;
    read_int(n);
    for (int i = 1; i <= n; ++i) {
      read_int(p[i]);
    }
    memset(dp, 0x3f, (n + 2) * sizeof(dp[0]));
    dp[1][0][0] = -n - 1;
    dp[1][0][1] = -n - 1;
    for (int i = 1; i <= n - 1; ++i) {
      for (int cur_pos = 0; cur_pos <= 1; ++cur_pos) {
        for (int cur_sign = 0; cur_sign <= 1; ++cur_sign) {
          if (dp[i][cur_pos][cur_sign] > n) continue;
          int x = p[i] * (cur_sign * 2 - 1);
          int y = dp[i][cur_pos][cur_sign];
          if (cur_pos) swap(x, y);
          for (int next_sign = 0; next_sign <= 1; ++next_sign) {
            int z = next_sign == 0 ? -p[i + 1] : p[i + 1];
            if (z > x) {
              if (y < dp[i + 1][0][next_sign]) {
                pre[i + 1][0][next_sign][0] = cur_pos;
                pre[i + 1][0][next_sign][1] = cur_sign;
                dp[i + 1][0][next_sign] = y;
              }
            } else if (z > y) {
              if (x < dp[i + 1][1][next_sign]) {
                pre[i + 1][1][next_sign][0] = cur_pos;
                pre[i + 1][1][next_sign][1] = cur_sign;
                dp[i + 1][1][next_sign] = x;
              }
            }
          }
        }
      }
    }
    int cur_pos = -1, cur_sign = -1;
    for (int i = 0; i <= 1; ++i) {
      for (int j = 0; j <= 1; ++j) {
        if (dp[n][i][j] <= n) {
          cur_pos = i;
          cur_sign = j;
          break;
        }
      }
    }
    if (cur_pos == -1) {
      puts("NO");
      continue;
    }
    puts("YES");
    for (int i = n; i >= 1; --i) {
      if (cur_sign == 0) p[i] = -p[i];
      int tpos = cur_pos;
      cur_pos = pre[i][tpos][cur_sign][0];
      cur_sign = pre[i][tpos][cur_sign][1];
    }
    for (int i = 1; i <= n; ++i) {
      printf("%d ", p[i]);
    }
    puts("");
  }
  return 0;
}

```