Balloons

Interview

Time limit2sMemory limit256 MB

Summary

Given n balloons with colors and a number k, choose exactly k balloons so the number of distinct colors is maximized, and print their colors.

Level: Medium4 of 10
Topics: Greedy, Hash map, Sorting, Implementation
Solved: No attempts yet

Problem

Today is Gru's birthday, and the Minions decided to give him a set of balloons in various colors.

Gru turns exactly k years old, so they decided to give him k balloons. Since many balloons of the same color are boring, you are asked to choose exactly k of the available balloons so that the number of distinct colors among the chosen balloons is as large as possible.

Input

The first line contains two integers n and k (1 ≤ k ≤ n ≤ 105). n is the number of balloons the Minions have, and k is the number of balloons they decided to give Gru. The next line contains n integers a_i (1 ≤ a_i ≤ 109). a_i is the color of a balloon.

Output

Print exactly k integers separated by spaces: the colors of the balloons to give Gru. If there are several correct answers, print any of them.

Examples2

Example 1
Input
```
5 3
1 1 1 2 2
```
Expected output
```
1 1 2
```
Example 2
Input
```
10 4
8 8 8 8 8 8 8 8 2 1
```
Expected output
```
1 2 8 8
```