Description

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

But he completely misunderstood what frequency analysis is.

He intercepted an enemy message. The message consists of $N$ numbers, each not greater than $C$.

Mirko believes that frequency analysis means sorting the sequence so that numbers with higher frequency come before numbers with lower frequency.

For any two numbers $x$ and $y$, if the number of occurrences of $x$ in the original sequence is greater than the number of occurrences of $y$, then $x$ should appear before $y$. If the numbers of occurrences are equal, then whichever value appears earlier in the input should appear earlier in the sorted sequence.

Please help Mirko build a "frequency sorter".

Input Format

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

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

Output Format

Output one line with $N$ positive integers, representing the sorted sequence.

5 2
2 1 2 1 2

2 2 2 1 1

9 3
1 3 3 3 2 2 2 1 1

1 1 1 3 3 3 2 2 2

9 77
11 33 11 77 54 11 25 25 33

11 11 11 33 33 25 25 77 54

Hint

Constraints

For $100\%$ of the testdata, $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 points. Each test case is worth 7 points, for a total of 10 test cases.

Translated by ChatGPT 5