After birth, all babies are registered to the National Civil Registration Office (NCRO). The office publishes popular names periodically.

Question: Write a program that reads names of and gender of n babies from NCRO database. Then, your program must show the top popular m boy and girl names.

Input specification: You will be given two integers in the first line: (n) number of babies, (m) number of names to list. Starting from the second line, you will be given a char (F or M) and a name. The names contain only 26 English uppercase or lowercase letters and 1 ≤ m < n ≤ 50,0000.

Output specification: In the first line, show top popular m girl names Then, show top popular m boy names. Note: If there are baby names with the same number appearances, show them in ascending order according to the names.

Explanation for sample input 1: There are 3 Shelly; 1 Luz; and 1 Whitney. Because Luz and Whitney appear the same number of times, they are shown in ascending order according to the names. So, Shelly and Luz.

There are 3 different boy names: 1 Casey; 2 Leon; 2 Scott. As a result: Leon and Scott are the most common boy names in this period.