D - Bridge

Time limit: 1 s
Memory limit: 256 MiB
Languages: C, C++, Java, Python, ... (details)

Fito has a new box of colored cubes. Since he is so eager to play with them, he wishes to build a bridge by placing all cubes in a row. However, to build an elegant bridge, there must not exist two consecutive cubes of the same color. As if this were not enough, Fito decided that the first and last cubes on the bridge have specific colors. Your task is to help Fito determine a distribution of the cubes to build the bridge.


First, there is a line with an integer $t$ denoting the number of test cases. Every test case consists of two lines. The first line has four integers $n$, $k$, $p$ and $q$ $(1 \le n, k \le 10^5$, $1 \le p, q \le k)$, the number of cubes, the number of colors, the color of the first and the last cube in the row, respectively. The second line contains $n$ integers $a_i$ $(1 \le a_i \le k)$, the color of each cube. It is guaranteed that the total number of cubes among all testcases is at most $10^5$.


For every test case, print $\texttt{"No"}$ (without quotes) if there is no way to distribute the cubes to build the bridge that satisfies Fito constraints, or $\texttt{"Yes"}$ (without quotes) otherwise. Additionally, if there is a solution, print $n$ integers (the colors) in the order that Fito must place each block to build the bridge. Any valid answer will be accepted. Note that ALL cubes must be used.

Sample test(s)

3 1 1 1 1 1 8 3 3 1 2 2 2 2 3 3 1 1 8 3 3 1 3 3 3 2 2 2 1 1
Yes 1 No Yes 3 2 3 2 3 1 2 1