Team Sorting for Extracurricular Activity

In this problem, you are given the current lineup of students in a class. The teacher instructed to split the class into two teams based on gender (boys and girls) and then sort each team by height in increasing order. However, due to a misunderstanding, the students are already standing in a single line. Your task is to help form two teams by separating the students by their gender and sorting each team by height in ascending order.

More formally, the input begins with an integer n, representing the number of students. The following n lines each consist of a character and an integer, where the character is either 'M' (for male) or 'F' (for female), and the integer represents the student’s height. You should output two lines: the first containing the heights of the boys in sorted order, and the second containing the heights of the girls in sorted order. If a team is empty, output an empty line for that team.

The sorting in each team should be in increasing order (i.e. from shortest to tallest).

inputFormat

The first line contains a single integer n (1 ≤ n ≤ 10^5), indicating the number of students. Each of the following n lines contains a character and an integer separated by a space. The character is either 'M' for male or 'F' for female, and the integer represents the height of the student.

outputFormat

Print two lines. The first line contains the heights of all male students in ascending order, separated by a space. The second line contains the heights of all female students in ascending order, separated by a space. If there are no students of a particular gender, output an empty line for that team.

sample

5
M 170
F 160
M 165
F 155
F 168

165 170
155 160 168