---
title: Blocks
---

You have $n$ wooden blocks of $k$ different colors arranged in a line. The colors of the blocks are $c_1, c_2, \dots, c_n$, all between $1$ and $k$.

A color is _balanced_ if the average position of blocks with that color is $(n+1)/2$. Note that this number is not necessarily an integer.

![Blocks with colors 1, 2, 2, 1, 3, 1, 2](files/blocks.svg "=440x")

For example, if $7$ blocks are arranged in the above way, the average position of color $1$ is $(1 + 4 + 6) / 3 = 11/3$, the average position of color $2$ is $(2 + 3 + 7) / 3 = 4$ and the average position of color $3$ is $5$. Since $(7+1)/2=4$, color $2$ is balanced but colors $1$ and $3$ are not.

Can you order the blocks in such a way that all colors are balanced?

# Input

The first line contains a single integer $t$: the number of test cases.

The following lines describe the test cases, each consisting of two lines as follows:

The first line contains two integers $n$ and $k$: the number of blocks and the number of different colors.

The second line contains the colors of the blocks $c_1, c_2, \dots, c_n$. There is at least one block of each color.

# Output

For each test case, print "`YES`" if a solution exists, and "`NO`" otherwise. If a solution exists, describe one possible order by printing $n$ integers on another line: the color of the block in each position.

# Constraints

- $1 \le t \le 100$
- $1 \le k \le n \le 2 \cdot 10^5$
- $1 \le c_1, c_2, \dots, c_n \le k$
- The sum of all $n$ is at most $2 \cdot 10^5$

# Example

Input:
```
3
7 2
1 1 1 1 2 2 2
2 2
1 2
2 1
1 1
```

Output:
```
YES
1 2 2 1 1 1 2
NO
YES
1 1
```

_Explanation_: In the output of the first test case, color $1$ is balanced because its average position is $(1 + 4 + 5 + 6) / 4 = 4$, which equals $(n + 1) / 2$. Similarly, the average position of color $2$ is $(2 + 3 + 7) / 3 = 4$. Both colors are therefore balanced.

In the second test case, neither of the two possible orders make the colors balanced.

In the output of the third test case, blocks with color $1$ appear at positions $1$ and $2$. The average is $3/2$, so color $1$ is balanced.

# Scoring

| Subtask | Constraints | Points    |
| :-----: | ----------- | :-------: |
| 1       | $n \le 3$   | [score=1] |
| 2       | $n \le 15$  | [score=2] |
| 3       | There is at most one color that appears an odd number of times | [score=3] |
| 4       | All colors appear an equal number of times | [score=4] |
| 5       | $k \le 15$  | [score=5] |
| 6       | No additional constraints | [score=6] |
