P16456 [UOI 2026] Intersection of Prefix Sums

You are given an array $a$ of $n$ integers and an integer $x$. You need to rearrange the elements of the array so that in the resulting array there is no $\textbf{non-empty}$ prefix with sum equal to $x$, or report that this is impossible. In other words, you need to find a permutation $p_1, p_2, \dots, p_n$ of the elements of array $a$ such that for every $k$ $(1 \le k \le n)$ the following holds: $p_1 + p_2 + \dots + p_k \neq x.$

The first line contains one integer $t$ $(1 \le t \le 10^4)$~--- the number of test cases. Each test case consists of two lines. The first line of each test case contains two integers $n$, $x$ $(1 \le n \le 10^5, |x| \le 10^{15})$ --- the number of elements in the array and the forbidden prefix sum. The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ $(|a_i| \le 10^9)$ --- the elements of the array. It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.

For each test case, output the answer in the following format. In the first line, output $\texttt{YES}$ if there exists a permutation of array $a$ with no non-empty prefix whose sum is $x$. Otherwise, output $\texttt{NO}$. If the answer is $\texttt{YES}$, then in the second line output $n$ integers separated by spaces --- the required permutation of array $a$. If there are multiple correct permutations, you may output any of them. The strings $\texttt{YES}$ and $\texttt{NO}$ may be printed in any case. For example, $\texttt{yes}$, $\texttt{Yes}$, and $\texttt{YES}$ will all be considered the same. For each block, you can receive $\textbf{half of the points}$ if for every test case in that block you correctly determine whether the required permutation exists. That is, to obtain half of the points, it is enough to correctly output $\texttt{YES}$ or $\texttt{NO}$ for each test case of the corresponding subtask. Note that if you output $\texttt{YES}$, then the next line must contain exactly $n$ integers separated by spaces. To obtain $\textbf{full points}$, these $n$ integers must form a permutation of array $a$ that does not contain a non-empty prefix with sum $x$. To obtain $\textbf{half}$ of the points, these $n$ integers may be arbitrary. They may even not be elements of array $a$. If after $\texttt{YES}$ you do not output exactly $n$ integers, then you cannot get even half of the points for that test case. For example, suppose that for some test case $n = 5$ and the correct answer is $\texttt{YES}$. Then for half of the points you may output: ``` YES 1 1 1 1 1 ``` even if array $a$ does not contain such numbers. But you cannot output only: ``` YES ``` In that case, after $\texttt{YES}$, a line with exactly $n$ integers in the range $[-10^9; 10^9]$ is not output.

### Note In the first example, there exists a permutation $[2, 1, 2, 1, -3, 2]$. The prefix sums of this sequence are $[2, 3, 5, 6, 3, 5]$ and do not contain the number $4$. There are also other permutations that work. In the second example, there is only one permutation, and its prefix sums contain the number $7$. ### Scoring - ($2$ points): $a_i = a_1$ for all $i$; - ($4$ points): $x = 0$; - ($4$ points): $t = 1$, $n \le 9$; - ($6$ points): $t = 1$, $n \le 15$; - ($8$ points): $a_i > 0$ for all $i$, $x \le 200$; - ($14$ points): the array contains at most two distinct values; - ($10$ points): if a correct permutation exists, it can be obtained by swapping the first element of the array with some other element; - ($12$ points): $a_i > 0$ for all $i$; - ($16$ points): the array contains exactly one negative number; - ($24$ points): no additional constraints.