Problem Description

Mirko is a great codebreaker. He knows that any password in the world can be cracked by frequency analysis.

But he completely misunderstands what frequency analysis is.

He intercepted an enemy message. This message consists of $N$ numbers, each less than or equal to $C$.

Mirko believes that frequency analysis involves sorting this sequence such that numbers with higher frequencies appear before those with lower frequencies.

Given any two numbers $x$ and $y$, $x$ should appear before $y$ if $x$ occurs more frequently than $y$ in the original sequence. If their frequencies are equal, the number that appears earlier in the input should appear earlier in the sorted sequence.

Please help Mirko create a "frequency sorter".

Input Format

The first line contains two positive integers $N, C$, as described in the problem statement.

The second line contains $N$ positive integers $a_i$, representing the message.

Output Format

The first line should contain $N$ positive integers, representing the sorted sequence.

Sample Input and Output

Sample Input #1

5 2
2 1 2 1 2

Sample Output #1

2 2 2 1 1

Sample Input #2

9 3
1 3 3 3 2 2 2 1 1

Sample Output #2

1 1 1 3 3 3 2 2 2

Sample Input #3

9 77
11 33 11 77 54 11 25 25 33

Sample Output #3

11 11 11 33 33 25 25 77 54

Notes

Data Size and Constraints

For $100\%$ of the data, $1 \le N \le 10^3$, $1 \le C \le 10^9$, and $1 \le a_i \le C$.

Notes

Translated from COCI 2009-2010 #3 T3 SORT, full score is 70, each test case is worth 7 points, with a total of 10 test cases.

见题面 Input 部分

见题面 Output 部分