No tag edit access

D. Cutting Out

time limit per test

3 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou 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.

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/22/2019 07:46:38 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|