RKS - RK Sorting

RK is a great code breaker. He knows any cipher in the world can be broken by frequency analysis. He intercepted an enemy message. The message consists of N numbers, smaller than or equal to C. RK belives freqency analysis consists of sorting this sequence so that more frequent numbers appear before less frequent ones.

Formally, the sequence must be sorted so that given any two numbers X and Y , X appears before Y if the number of times X appears in the original sequence is larger than the number of time Y does. If the number of appearances is equal, the number whoes value appears sooner in the input should appear sooner in the sorted sequence.
Help RK by creating a "frequency sorter".

Input

First line of input contains two integers, N (1 <= N <= 1000), length of message, and C (1 <= C <= 10^9), the number from task description. Next line contains N integers smaller than or equal to C, message itself.

Output

First and only line of output should contain N numbers, the sorted sequence.

Sample

Input
9 3
1 3 3 3 2 2 2 1 1

Output
1 1 1 3 3 3 2 2 2
Input
5 2
2 1 2 1 2

Output
2 2 2 1 1

Added by:BLANKRK
Date:2014-01-28
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64

hide comments
2014-03-03 02:53:03 785227
STL rocksssssss ... AC at first attempt... Great problem
2014-02-18 22:01:58 apg7
My 100th..:)
2014-02-16 21:51:21 Ouditchya Sinha
Nice Problem! Enjoyed solving it. :)
2014-02-14 11:30:33 yaswanth
piece of cake using STL :)
2014-02-12 18:14:29 bale
ac in one go....still a nice prbl....

Last edit: 2014-02-27 18:09:05
2014-02-11 17:29:12 Jumpy
thought would be difficult..
2014-02-04 23:36:39 JordanBelfort
easy :)
2014-02-04 15:42:32 anurag garg
difficult for me....finally AC
2014-02-01 18:07:11 Bhavik
certainly not difficult...nice implementation though:)

Last edit: 2014-02-01 18:32:29
2014-01-31 11:09:26 wisfaq
@Lakshman: read the first paragraph.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.