The Retaliation of Reality

All submissions for this problem are available.
**A long journey awaits the one who progresses. Hurdles are plentiful, but are better overcome with skill rather than complication.** With the fall of a mighty avenger, Thanos is on a rampage. He wishes to fulfill his desire of fulfilling his never ending set of desires. Sounds puzzling, right? Well, read on to unravel the mystery. The collector has cleverly used the Reality stone to create $N$ alternate realities, confusing the person who wishes to obtain it. But in his nervousness, he has actually created a **multiset** of realities, where realities may be duplicated. Each reality may be described by an integer **X_{i}**, denoting its **reality quotient**. The collector has also left behind a note, stating that the one who wishes to obtain the stone must write out exactly $K$ reality quotients, such that their **embedding power** is largest. Note that the set of chosen realities may be a **multiset** too. The **embedding power** of a set of realities is obtained as follows: Let $S$ be the set of chosen reality quotients. For every element of set $S$, remove **exactly one** of its occurrences in the set of $N$ reality quotients. The **embedding power** is the maximum number of times one can repeat this process until it is no longer possible. Furthermore, the embedding power is maximum for a set that is **lexicographically smallest** when **sorted in ascending order.** A sequence $p$ is said to be lexicographically smaller than a sequence $q$ if: There exists an index **i** such that **p_{i} $\lt$ q_{i}** and **p_{j} $=$ q_{j}** for all **j $\lt$ i**, or $p$ matches $q$ completely and $q$ is longer. Find the sorted order of the set of realities that has the largest embedding power, if you desire that all you will be true. ###Input Format: The first line of input contains $T$, the number of test cases. Each test case is described as follows: The first line contains two space separated integers $N$ and $K$, as described earlier. The second line contains $N$ space separated integers, denoting the values of the reality quotients. ###Output Format: Print a single line for each test case, the set that maximizes the embedding power. ###Constraints:  $1$ $\leq$ $T$ $\leq$ **10^{5}**  $1$ $\leq$ $N$ $\leq$ **10^{5}**  $0$ $\leq$ $K$ $\leq$ $N$  $$**10^{18}** $\leq$ **X_{i}** $\leq$ **10^{18}**  The sum of $N$ over all test cases doesn't exceed **10^{6}** ###Sample Input: 2 5 2 1 2 3 4 5 7 3 2 1 1 4 5 3 6 ###Sample Output: 1 2 1 1 2 ###Explanation: For the first testcase, there are many optimal sets, namely **{1,2},{1,3},{1,4},{1,5},{2,3},{2,4},{2,5},{3,4},{3,5},{4,5}**, and the least one is **{1,2}**.Author:  bluishgreen 
Tags  bluishgreen 
Date Added:  19122018 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions