Minimal Difference Partition

You are given an integer x and an array of n integers. Your task is to partition the array into x subarrays such that when the original array is sorted in ascending order, dividing it into x nearly equal parts minimizes the range within each subarray. Each partition is defined using the formula:

\(\text{Partition } i: [\lfloor \frac{i\times n}{x} \rfloor, \lfloor \frac{(i+1)\times n}{x} \rfloor - 1]\)

After partitioning, sort each subarray individually (although they will already be sorted as a result of the initial sort) and output the concatenation of these subarrays. This procedure guarantees that the maximum difference within each partition is minimized while preserving the overall order.

Note: The input is provided through standard input and the output should be printed to standard output.

inputFormat

The first line contains two integers x and n, where x is the number of partitions and n is the number of elements in the array. The second line contains n space-separated integers.

outputFormat

Output the resulting array after performing the partitioning and concatenation. The numbers should be printed in a single line separated by spaces.

3
7
1 9 8 3 5 6 7

1 3 5 6 7 8 9