Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

D. Cutting Out
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array $$$s$$$ consisting of $$$n$$$ integers.

You have to find any array $$$t$$$ of length $$$k$$$ such that you can cut out maximum number of copies of array $$$t$$$ from array $$$s$$$.

Cutting out the copy of $$$t$$$ means that for each element $$$t_i$$$ of array $$$t$$$ you have to find $$$t_i$$$ in $$$s$$$ and remove it from $$$s$$$. If for some $$$t_i$$$ you cannot find such element in $$$s$$$, then you cannot cut out one more copy of $$$t$$$. The both arrays can contain duplicate elements.

For example, if $$$s = [1, 2, 3, 2, 4, 3, 1]$$$ and $$$k = 3$$$ then one of the possible answers is $$$t = [1, 2, 3]$$$. This array $$$t$$$ can be cut out $$$2$$$ times.

  • To cut out the first copy of $$$t$$$ you can use the elements $$$[1, \underline{\textbf{2}}, 3, 2, 4, \underline{\textbf{3}}, \underline{\textbf{1}}]$$$ (use the highlighted elements). After cutting out the first copy of $$$t$$$ the array $$$s$$$ can look like $$$[1, 3, 2, 4]$$$.
  • To cut out the second copy of $$$t$$$ you can use the elements $$$[\underline{\textbf{1}}, \underline{\textbf{3}}, \underline{\textbf{2}}, 4]$$$. After cutting out the second copy of $$$t$$$ the array $$$s$$$ will be $$$[4]$$$.

Your task is to find such array $$$t$$$ that you can cut out the copy of $$$t$$$ from $$$s$$$ maximum number of times. If there are multiple answers, you may choose any of them.

Input

The first line of the input contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 2 \cdot 10^5$$$) — the number of elements in $$$s$$$ and the desired number of elements in $$$t$$$, respectively.

The second line of the input contains exactly $$$n$$$ integers $$$s_1, s_2, \dots, s_n$$$ ($$$1 \le s_i \le 2 \cdot 10^5$$$).

Output

Print $$$k$$$ integers — the elements of array $$$t$$$ such that you can cut out maximum possible number of copies of this array from $$$s$$$. If there are multiple answers, print any of them. The required array $$$t$$$ can contain duplicate elements. All the elements of $$$t$$$ ($$$t_1, t_2, \dots, t_k$$$) should satisfy the following condition: $$$1 \le t_i \le 2 \cdot 10^5$$$.

Examples
Input
7 3
1 2 3 2 4 3 1
Output
1 2 3 
Input
10 4
1 3 1 3 10 3 7 7 12 3
Output
7 3 1 3
Input
15 2
1 2 1 1 1 2 1 1 2 1 2 1 1 1 1
Output
1 1 
Note

The first example is described in the problem statement.

In the second example the only answer is $$$[7, 3, 1, 3]$$$ and any its permutations. It can be shown that you cannot choose any other array such that the maximum number of copies you can cut out would be equal to $$$2$$$.

In the third example the array $$$t$$$ can be cut out $$$5$$$ times.