Rearrange List Elements

You are given a list of integers and an integer n. Your task is to rearrange the list by moving every n-th element to the front while preserving their original relative order, and then append the remaining elements sorted in ascending order.

More formally, let the list be represented as \(a_1, a_2, \dots, a_m\). You should extract the elements \(a_n, a_{2n}, \dots\) (if any) in order, and then take the remaining elements, sort them in increasing order, and finally, output the concatenation of these two lists.

Note: It is guaranteed that \(n > 0\). In case \(n\) exceeds the number of elements in the list, simply output the sorted list.

For example, if the input list is [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5] and n = 3, the every 3rd element is [4, 9, 5] (as these are the 3^rd, 6^th, and 9^th elements). The remaining elements [3, 1, 1, 2, 6, 3, 5] sorted in ascending order become [1, 1, 2, 3, 3, 5, 6]. Thus, the final output is [4, 9, 5, 1, 1, 2, 3, 3, 5, 5, 6].

inputFormat

The input is given via standard input and consists of three lines:

• The first line contains an integer m denoting the number of elements in the list.
• The second line contains m space-separated integers representing the list.
• The third line contains an integer n.

You can assume that m \(\geq 0\) and n > 0.

outputFormat

Print the rearranged list as space-separated integers on a single line.

11
3 1 4 1 5 9 2 6 5 3 5
3

4 9 5 1 1 2 3 3 5 5 6