Limits
2s, 512 MB

Zenitsu has been elected as the president of RUET FC and now he wants to sign some of the best world-class football players into his team.

Initially he has a list of $n$ unique players named $s_1, s_2, s_3, \cdots, s_n$. But it is not possible for him to evaluate the talent of all the players all by himself because he has so many other important works to do.

So he has hired $m$ scouts who will report to him. Each of the scouts will send a list of players that seemed good to them and Zenitsu will choose the players who were mentioned most of the time by the scouts. However, the list of players the scouts will send might have names of players who are not on the initial list. Being the new president, Zenitsu is very busy reconstructing the club. That’s why he has asked you to do a favor. He wants you to make the list of the players in lexicographical order who were mentioned most of the time by the scouts and are in the initial list of Zenitsu.

A string $a$ is lexicographically smaller than a string $b$ if and only if one of the following conditions holds:

$a$ is a prefix of $b$, but $a \neq b$.

In the first position where $a$ and $b$ differs, the string $a$ has a letter that appears earlier in the alphabet than the corresponding letter in $b$.

The first line of the input will contain two integers $n (1 \leq n \leq 10^6)$ and $m(1 \leq m \leq 1000)$, the number of players in the initial list and the number of hired scouts.

The following $n$ lines will contain a string, the names of the players in the initial list. Each name will contain at most $10$ lowercase and uppercase letters of the English alphabet. It is guaranteed that each name will be mentioned at most once.

The following $m$ lines will contain an integer $(1 \leq q \leq 1000)$ and each of the following $q$ lines will contain a string, the names of the players each scout chose. Each name will contain at most $10$ lowercase and uppercase letters of the English alphabet. It is guaranteed that each scout will mention each player’s name at most once.

All the names here are case sensitive which means “Jesse”, “jesse”, “JesSE”, “jESsE” etc are not the same names.

Output the number of players that were chosen finally and print their names in lexicographical order.

Input | Output |
---|---|

5 3 Goodman Mike Jesse Walter Tuco 4 Gus Goodman Jesse Tuco 3 Gus Goodman Walter 3 Gus Jesse Mike | 2 Goodman Jesse |

Login to submit.

82%
Solution Ratio

Mahi175Earliest,

FAHIM.ctgFastest, 1.0s

user.051537Lightest, 80 MB

FAHIM.ctgShortest, 863B

Toph uses cookies. By continuing you agree to our Cookie Policy.