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
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

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

/*
stream Butter!
eggyHide eggyVengeance
I need U
xiao rerun when
 */
import static java.lang.Math.*;
import java.util.*;
import java.io.*;
import java.math.*;

public class x1620F
{
    static final int INF = Integer.MAX_VALUE/2;
    public static void main(String hi[]) throws Exception
    {
        BufferedReader infile = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(infile.readLine());
        int T = Integer.parseInt(st.nextToken());
        StringBuilder sb = new StringBuilder();
        while(T-->0)
        {
            st = new StringTokenizer(infile.readLine());
            int N = Integer.parseInt(st.nextToken());
            int[] arr = readArr(N, infile, st);
            if(N <= 2)
            {
                sb.append("YES\n");
                for(int x: arr)
                    sb.append(x+" ");
                sb.append("\n");
                continue;
            }
            ArrayList<State> curr = new ArrayList<State>();
            curr.add(new State(INF, arr[0], arr[0], null));
            curr.add(new State(INF, -arr[0], -arr[0], null));
            for(int i=1; i < N; i++)
            {
                ArrayList<State> next = new ArrayList<State>();
                for(int m=-1; m <= 1; m+=2)
                {
                    int val = arr[i]*m;
                    for(State prev: curr)
                    {
                        if(prev.x == INF)
                        {
                            if(prev.y > val)
                                next.add(new State(prev.y, val, val, prev));
                            else
                                next.add(new State(INF, val, val, prev));
                        }
                        else
                        {
                            if(val > prev.x)
                                next.add(new State(val, prev.y, val, prev));
                            else if(val > prev.y)
                                next.add(new State(prev.x, val, val, prev));
                        }
                    }
                }
                boolean[] useful = new boolean[next.size()];
                Arrays.fill(useful, true);
                for(int aa=0; aa < next.size(); aa++)
                    for(int bb=0; bb < next.size(); bb++)
                        if(aa != bb)
                        {
                            State a = next.get(aa);
                            State b = next.get(bb);
                            if(a.x != INF && b.x != INF)
                            {
                                if(a.x >= b.x && a.y >= b.y)
                                {
                                    useful[aa] = false;
                                    break;
                                }
                            }
                            else if(a.x == INF && b.x == INF)
                            {
                                if(a.y >= b.y)
                                {
                                    useful[aa] = false;
                                    break;
                                }
                            }
                        }
                curr.clear();
                for(int a=0; a < next.size(); a++)
                    if(useful[a])
                        curr.add(next.get(a));
            }
            if(curr.size() == 0)
                sb.append("NO\n");
            else
            {
                sb.append("YES\n");
                ArrayList<Integer> res = new ArrayList<Integer>();
                State node = curr.get(0);
                while(node != null)
                {
                    res.add(node.val);
                    node = node.parent;
                }
                Collections.reverse(res);
                for(int x: res)
                    sb.append(x+" ");
                sb.append("\n");
            }
        }
        System.out.print(sb);
    }
    public static int[] readArr(int N, BufferedReader infile, StringTokenizer st) throws Exception
    {
        int[] arr = new int[N];
        st = new StringTokenizer(infile.readLine());
        for(int i=0; i < N; i++)
            arr[i] = Integer.parseInt(st.nextToken());
        return arr;
    }
}
class State
{
    public int x;
    public int y;
    public int val;
    public State parent;

    public State(int a, int b, int t, State par)
    {
        x = a;
        y = b;
        val = t;
        parent = par;
    }
}