Lexicographically Largest Sort

Interview

Time limit2sMemory limit128 MB

Summary

Given a distinct-integer array and a budget of at most S adjacent swaps, output the lexicographically largest array reachable within that swap budget.

Level: Medium5 of 10
Topics: Greedy, Array, Simulation
Solved: No attempts yet

Problem

You are given an array A of size N. All elements of the array are distinct.

In one operation, you may swap two adjacent elements. You may perform at most S operations. Among all arrays obtainable this way, print the lexicographically largest one.

Input

The first line contains a positive integer N. N is at most 50.

The second line contains the N elements of array A in order. The elements are distinct positive integers between 1 and 1,000,000, inclusive.

The third line contains a nonnegative integer S. S is at most 1,000,000.

Output

Print the array satisfying the condition on the first line, with elements separated by spaces.

Examples3

Example 1

Input

7
10 20 30 40 50 60 70
1

Expected output

20 10 30 40 50 60 70

Example 2
Input
```
5
3 5 1 2 4
2
```
Expected output
```
5 3 2 1 4
```

Example 3

Input

10
19 20 17 18 15 16 13 14 11 12
5

Expected output

20 19 18 17 16 15 14 13 12 11