Cutting Out
Contest: Codeforces Round 521 (Div. 3)
Difficulty rating: 1600
Tags: binary search, sortings

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 format:
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 format:
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$$$.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

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.

Example input:
7 3
1 2 3 2 4 3 1

Example output:
1 2 3

Example input:
10 4
1 3 1 3 10 3 7 7 12 3

Example output:
7 3 1 3

Editorial:
Let's solve the problem using binary search by the answer. It is easy to see that if we can construct the answer for some number of copies $$$val$$$ then we also can do it for $$$val - 1$$$. The only thing we need is to write the function $$$can(val)$$$ which will say can we cut off $$$val$$$ copies of some array $$$t$$$ from $$$s$$$ or not.
Let's imagine $$$val$$$ copies of string $$$t$$$ as a matrix of size $$$val \times k$$$. Obviously, each row of this matrix should be equal to each other row. Let's fill not rows but columns of this matrix. For some element $$$i$$$ of $$$s$$$ we can easy notice that we can take exactly $$$\lfloor\frac{cnt_i}{val}\rfloor$$$ columns containing this element where $$$cnt_i$$$ is the number of such elements in $$$s$$$. So, overall number of columns we can fill in this matrix will be $$$\sum\limits_{i = 1}^{2 \cdot 10^5} \lfloor\frac{cnt_i}{val}\rfloor$$$. If this value is greater than or equal to $$$k$$$ then $$$can(val)$$$ is true otherwise it is false.
It is easy to construct the answer using all things we described above.
Overall complexity is $$$O(n + |A|\log n)$$$ where $$$|A|$$$ is the size of the alphabet.