Problems
Gratitude
Gratitude
Ben heard about studies by Emmons and McCullough that suggest that intentionally practicing gratitude has a lasting effect on people's happiness. Since he wants to be happy too, he decided that at the end of each day he will think back over the past day and write down three things he is thankful for, one thing per line. At the end of $n$ days in which he practiced this exercise, he was curious to know which things appeared most frequently on his list. Help Ben obtain the $k$ items for which he was frequently grateful.
\InputFile
The first line contains two integers $n$ and $k~(1 \le k \le 3 \cdot n \le 10^5)$. Then follow $3 \cdot n$ lines containing Ben’s notes from $n$ days. You may assume that the three lines that correspond to the same day contain no repetitions. That is, no chunk contains two identical lines if the input is divided into $n$ chunks of $3$ consecutive lines.
Each line contains at most $50$ (ASCII) characters.
\OutputFile
The output should represent the list of things that Ben is grateful for, ordered by frequency of appearance in Ben’s list (with the most frequent item first). When two items have the same frequency, the most recent item should appear first. That is, in case of a tie in the number of appearances, the item whose last appearance is later in the input should appear earlier in the output. Finally, if there are more than $k$ different items in Ben’s list, your output should contain only the $k$ first items (according to the required order).
\Examples
Sample 1. "Good food" is the only item that appears twice in Ben's list, so it should appear first in the output. All other items appear once in the input, but "Being healthy" takes precedence as it is the most recent.
Sample 2. Here there are only $5$ different items that Ben is grateful for, so there are only $5$ lines of output. In this list, "Good food" is first in the output since it appears twice in the input, and the other items are ordered by last appearance in Ben's list.
Input example #1
2 2 Supportive parents Being able to solve a hard problem Good food Fun game with friends Good food Being healthy
Output example #1
Good food Being healthy
Input example #2
2 6 Supportive parents Being able to solve a hard problem Good food Fun game with friends Good food Being healthy
Output example #2
Good food Being healthy Fun game with friends Being able to solve a hard problem Supportive parents