President of RUET FC

santo_ruet RUET CodeSmash 2020
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 nn unique players named s1,s2,s3,,sns_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 mm 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 aa is lexicographically smaller than a string bb if and only if one of the following conditions holds:

  • aa is a prefix of bb, but aba \neq b.

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

Input

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

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

The following mm lines will contain an integer (1q1000)(1 \leq q \leq 1000) and each of the following qq lines will contain a string, the names of the players each scout chose. Each name will contain at most 1010 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

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

Sample

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

Submit

Login to submit.

Statistics

82% Solution Ratio
Mahi175Earliest, 1M ago
FAHIM.ctgFastest, 1.0s
user.051537Lightest, 80 MB
FAHIM.ctgShortest, 863B
Toph uses cookies. By continuing you agree to our Cookie Policy.