Intersection of Prefix Sums#526

Intersection of Prefix Sums

0,3 seconde
256 mégaoctets
Hard

You are given an array of integers and an integer .

You need to rearrange the elements of the array so that in the resulting array there is no non-empty prefix with sum equal to , 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 such that for every (1 \le k \le n) the following holds: p_1 + p_2 + \dots + p_k \neq x.

Input

The first line contains one integer (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 , (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 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 over all test cases does not exceed 10^5.

Output

For each test case, output the answer in the following format.

In the first line, output «YES» if there exists a permutation of array with no non-empty prefix whose sum is . Otherwise, output «NO».

If the answer is «YES», then in the second line output integers separated by spaces — the required permutation of array .

If there are multiple correct permutations, you may output any of them.

The strings «YES» and «NO» may be printed in any case. For example, «yes», «Yes», and «YES» will all be considered the same.

For each block, you can receive 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 «YES» or «NO» for each test case of the corresponding subtask.

Note that if you output «YES», then the next line must contain exactly integers separated by spaces. To obtain full points, these integers must form a permutation of array that does not contain a non-empty prefix with sum .

To obtain half of the points, these integers may be arbitrary. They may even not be elements of array .

If after «YES» you do not output exactly 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 «YES». Then for half of the points you may output:

YES
1 1 1 1 1

even if array does not contain such numbers.

But you cannot output only:

YES

In that case, after «YES», a line with exactly integers in the range [-10^9; 10^9] is not output.

Examples

Example 1

Loading
Loading

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 . There are also other permutations that work.

In the second example, there is only one permutation, and its prefix sums contain the number .

Scoring

  1. ( points): a_i = a_1 for all ;

  2. ( points): x = 0;

  3. ( points): t = 1, n \le 9;

  4. ( points): t = 1, n \le 15;

  5. ( points): a_i > 0 for all , x \le 200;

  6. ( points): the array contains at most two distinct values;

  7. ( points): if a correct permutation exists, it can be obtained by swapping the first element of the array with some other element;

  8. ( points): a_i > 0 for all ;

  9. ( points): the array contains exactly one negative number;

  10. ( points): no additional constraints.