Reconstruct Last Week's Chart

Michael loves watching the weekly music TV rating list, where each song is listed according to its current ranking and accompanied by an indicator showing its ranking change from last week. Unfortunately, Michael missed the latest broadcast, but he knows that the next week’s list will reveal, for each song, a hint about how its ranking changed compared to last week.

You are given the current ranking of n songs along with a movement indicator for each song. For the current ranking position i (1-indexed):

• If the indicator is SAME, then the song's ranking last week was exactly i, i.e. \(p(i)=i\).
• If the indicator is UP, then the song has improved its position relative to last week. In other words, its last week ranking was worse: \(p(i) > i\).
• If the indicator is DOWN, then the song has dropped relative to last week. That is, its last week ranking was better: \(p(i) < i\).

Your task is to reconstruct a possible ordering (i.e. a permutation of \(\{1,2,\dots,n\}\)) for last week's chart that meets the conditions above. Here, for each song in the current list, you must assign a unique ranking from 1 through n such that the condition based on its movement indicator is satisfied.

Note: It is guaranteed that the input will allow at least one valid solution.

inputFormat

The first line contains a single integer n (the number of songs).

Each of the following n lines contains two items separated by a space: the song title (a string without spaces) and its movement indicator which is one of UP, DOWN, or SAME. The list is given in the order of the current ranking (with the first song being rank 1).

outputFormat

Output n lines, each containing the title of a song. The output should represent a possible ordering of last week’s chart sorted in ascending order of rank (i.e. the first line is the song at rank 1 last week, the second line is the song at rank 2, etc.).

sample

3
A SAME
B UP
C DOWN

A
C
B