#agc001f. [agc001_f]Wide Swap
[agc001_f]Wide Swap
Problem Statement
You are given a permutation of the set {, , ..., }.
You can apply the following operation to this permutation, any number of times (possibly zero):
- Choose two indices , such that and . Then, swap the values of and .
Among all permutations that can be obtained by applying this operation to the given permutation, find the lexicographically smallest one.
Constraints
- is a permutation of the set {, , ..., }.
Input
The input is given from Standard Input in the following format:
Output
Print the lexicographically smallest permutation that can be obtained.
Sample Input 1
4 2
4 2 3 1
Sample Output 1
2
1
4
3
One possible way to obtain the lexicographically smallest permutation is shown below:
Sample Input 2
5 1
5 4 3 2 1
Sample Output 2
1
2
3
4
5
Sample Input 3
8 3
4 5 7 8 3 1 2 6
Sample Output 3
1
2
6
7
5
3
4
8