Meditation
In Je'daii Order Academy a
meditation is conducted in a special room on daily basis. The masters come
first, and then knights, followed by the rookies. Regardless of the time when a
master arrives, he always stands before the knights and the rookies but not
before other masters. When a knight arrives he stands in line before all the
rookies but after other knights who are lined up. Ћarko
is a new rookie and would like to know exact schedule based on the signup
sheet.
Input: The
first line contains an integer N (0 < N <= 100 000) – number of Je'daiis. The second line contains the IDs of the Je'daiis separated by a space. Each ID consists of a letter
m (master), k (knight) or p (rookie) and a number. Ex: k12, m3, p111. The IDs
are unique and it contains at most 10 characters.
Output: Print
the IDs of ordered for the mediation separated by a space.
Example:
|
|
Test case 1
|
Test case 2
|
Test case 3
|
|
Input
|
3
m1 k1 p1
|
7
p4 p2 p3 m1 k2 p1 k1
|
5
k2 m2 m1 p1 k1
|
|
Output
|
m1 k1 p1
|
m1 k2 k1 p4 p2 p3 p1
|
m2 m1 k2 k1 p1
|
|
Explanation
|
No need to change
|
m1 goes before all; k2 is ahead of all rookies (p4, p2 and
p3) but behind m1. k1 is ahead of all
rookies (p4, p2, p3 and p1) is behind k2. No reordering of rookies is needed
|
m2, m1 before k2
k1 before p1.
|
Для отправки решений необходимо