Popularity List

Every Sunday afternoon a TV music show presents the same set of songs and, based on viewer votes, shows a popularity list (ranking) of those songs. Position 1 is the top of the list.

This week's list shows, for every position, the name of the song currently there together with a mark describing how that song moved compared with last week's list:

• UP — the song climbed to a better (smaller-numbered) position than it had last week.
• DOWN — the song fell to a worse (larger-numbered) position than it had last week.
• SAME — the song is at exactly the same position as last week.

You missed last week's list. Using this week's list and the movement marks, reconstruct a last week's list that is consistent with them.

In other words, a song marked UP at this week's position i occupied some last-week position greater than i; a song marked DOWN occupied some last-week position smaller than i; and a song marked SAME occupied position i last week too.

The first line contains an integer N (1 ≤ N ≤ 100), the number of songs on the list.

The next N blocks describe this week's list from position 1 to position N. Each block consists of two lines:

• the name of the song at that position — at most 100 uppercase English letters (A–Z);
• one of the words UP, DOWN, or SAME, describing how that song moved relative to last week.

For the given input at least one valid last-week list always exists. Song names are distinct.

Output last week's list as N lines: the i-th line contains the name of the song that occupied last-week position i.

Several last-week lists may be consistent with the input. Output the lexicographically smallest one: compare two candidate lists line by line from the top, and prefer the list whose first differing line holds the alphabetically smaller song name.