A child wants to give their parent a bouquet of flowers for their birthday. To do this, the child asks for help from a friend. The friend gives N flowers numbered 1 to N and instructs that the flowers in the bouquet be arranged in a particular order. The friend instructs that the first K flowers be arranged in order of increasing stem length and the remaining flowers in order of decreasing stem length.

Problem

Write an algorithm to find the final arrangement of the flowers in the bouquet.

Input

The first line of the input consists of an integer - flowerStem_size, representing the number of flowers (N). The second line consists of N space-separated integers - flowerStem1, flowerStem2, ......., flowerStemN representing the length of the flower stems. The last line consists of an integer - random, representing the number K.

Output

Print N space-separated integers representing the final arrangement of the flowers in the bouquet.

Constraints

• 0 ≤ random ≤ flowerStem_size
• 0 < flowerStem_size < 10^6