Wild cats take care of each other in the wild. However, when winter comes, the preys are not enough to feed all the cats.
In this problem, you are asked to help decide who can enjoy the precious food for three different categories of cats: apprentice, elder, and kitty.
First, the cats dine according to the following order of their occupations:
1. elder
2. kitty
3. apprentice
Then, except that the apprentices have the dining priority of the young over the old, for the other two occupations, the old have higher priority. If the occupations and the ages of two or more cats are the same, they will dine in lexicographic order according to their names.
There are multiple test cases.
The first line of each test case contains two integers N and M, indicating the number of cats and the portions of food respectively, where 0<N,M<=10000.
The next N lines are the information of each cat, including name, occupation, and age.
The length of the names will not exceed 30 letters and will contain no spaces.
Please output the cats that could eat the food in order, each name a line.