Determine the Best House by Median Scores

You are given a series of score entries from students belonging to one of the four Hogwarts houses: Gryffindor (G), Hufflepuff (H), Ravenclaw (R) and Slytherin (S).

Each entry consists of a house letter, a subject identifier, and a score. For each subject, your task is to determine which house has the highest median score. In the event of a tie (i.e. two or more houses have the same median score), choose the house with the lexicographically smallest identifier.

Note: The median of a list of numbers is defined as follows:

• If the count of numbers is odd, the median is the middle number after sorting.
• If the count is even, the median is the average of the two middle numbers (computed in real arithmetic).

The output should list the best house for each subject in ascending order of the subject identifiers, separated by a space.

inputFormat

The first line contains an integer n, the number of score entries. Each of the following n lines contains an entry with three fields separated by spaces: a house letter (one of G, H, R, S), an integer indicating the subject id, and an integer representing the score.

outputFormat

Output a single line containing the best house for each subject. The houses are listed in ascending order of subject ids and separated by a single space.## sample

4
G 0 90
H 0 85
R 0 88
S 0 91

S