Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Super Sort

By rumman13 · Limits 1s, 1.0 GB

Given an array of numbers and a non-negative integer KK you have to sort the array in such a way so that the absolute difference between every adjacent element is no more than KK.

For example if you have an array A=[8,7,6,9]A = [8, 7, 6, 9] and K=2K = 2 then one possible solution will be [8,9,7,6][8, 9, 7, 6] where 89=1,97=2,76=1|8 - 9| = 1, |9 - 7| = 2, |7 - 6| = 1 and the absolute difference between every adjacent elements are no more than 22.

If there is many solution you have to print the lexicographically smallest answer. If there are no solution just print No Solution\texttt{No Solution} .

Input

Input will start with a positive integer TT (0<T1500 < T \leq 150) denoting the number of test cases.

Each test case will have two positive integer NN (2N182 \leq N \leq 18) denoting the number elements in the array and KK (0K1030 \leq K \leq 10^3).

The next line will have NN space separated integers representing the array AA (103Ai103-10^3 \leq A_i \leq 10^3).

Output

For each test case if there is a solution print the lexicographically smallest sorted array. You have to print NN space separated integers without any leading or trailing spaces. If there are no solutions, print No Solution\texttt{No Solution}.

Sample

InputOutput
2
2 2
3 1
2 1
1 3
1 3
No Solution

Discussion

Toph uses cookies. By continuing you agree to our Cookie Policy.