K Nearest Neighbour (KNN) is a famous classification method. It finds the K-nearest neighbors according to given metric distance. Then, it decides the class of current object according to majority of the nearest neighbors.

Assuming K=4, the right image shows the four close neighbors in a circle (3 red dots and 1 green plus). Since the majority of the neighbors are red dots, then the test sample is assigned to the class of red dots.

Question: Write a program that is going to classify m points according to dataset given. Assume that a point is closer if its Euclidean distance is smaller. If Euclidean distances are the same then, the node which is alphabetically smaller is closer.

Input specification
First, you will be given two integers (n and K) where n is between 0 and 5000 and K is between 1 and 100. Then, in the following n lines, you will be given the information for n objects where every line contains the following information:

• x, y, z coordinates of the object where the coordinates are integers between -20000 and 20000
• the class of the object: a string not more than 10 chars

Output specification
Show the classes of m objects in m lines. If there are many classes having the same number of majority votes, assign the class which is alphabetically greater. e.g. red is alphabetically greater than blue.