Rearrange Array with Bounded Consecutive Difference

You are given an array of integers and an integer k. Your task is to rearrange the array such that the absolute difference between any two consecutive elements in the rearranged array is at most k. If no valid rearrangement exists, output -1.

Problem Analysis: It can be shown that if the array sorted in non-decreasing order does not satisfy the condition, then no permutation of the array can achieve a maximum difference of at most k between adjacent elements. Therefore, by sorting the array and verifying the condition on consecutive elements, you can determine whether a valid rearrangement exists.

Examples:

• For arr = [1, 2, 9, 12, 15, 16] and k = 3, the sorted array is [1, 2, 9, 12, 15, 16] and since |9-2| = 7 > 3, it is impossible to rearrange the array to satisfy the condition. Output: -1.
• For arr = [10, 3, 20] and k = 15, the sorted array is [3, 10, 20] and all differences are within k (|10-3| = 7, |20-10| = 10). Output: 3 10 20.
• For a single element array, e.g. [5], the output is simply 5.

inputFormat

The input is read from standard input (stdin) and has the following format:

n k
a1 a2 ... an

Where:

• n is an integer representing the number of elements in the array.
• k is the maximum allowed difference between any two consecutive elements.
• ai are the integers in the array.

outputFormat

The output is written to standard output (stdout). If a valid rearrangement exists, print the elements of the rearranged array in non-decreasing order, separated by a single space. If no valid rearrangement exists, output -1.

## sample

6 3
1 2 9 12 15 16

-1