You are given a list of integers of size N.

Write an algorithm to sort the first K elements (from list[0] to list[K-1]) of the list in ascending order, and sort the remaining elements (from list[K] to list[N-1]) in descending order.

Input Format

1. The first line contains an integer inputList_size, representing the number of elements in the list (N).
2. The next line contains N space-separated integers representing the elements of the list.
3. The last line contains an integer num, representing the number of elements to be sorted in ascending order (K).

Output Format

Print N space-separated integers representing the modified list.

Example

Input

8
11 7 5 10 46 23 16 8
3

Output

5 7 11 46 23 16 10 8

Explanation

• The first 3 elements are sorted in ascending order.
• The remaining elements are sorted in descending order.

First part:

11 7 5  →  5 7 11

Remaining part:

10 46 23 16 8  →  46 23 16 10 8

Hence, the final list is:

5 7 11 46 23 16 10 8