You are given an unordered array with n distinct numbers from 1 to n. You have to perform exactly k swaps and print the lexicographically largest array that can be obtained.

In one swap, you can choose any two distinct indices and swap the elements at those indices.

Input

First line consists of 2 integers n(1 < n ≤ 100000) and k(0 ≤ k ≤ 10⁹).

Next line consists of n integers (a₀, a₁, ... a_n-1).

Output

You have to print lexicographically largest array obtained.

Example

Input:
5 2
1 2 4 3 5
Output:
5 4 2 3 1