Description

Little Michael lives in a small town, and he likes to watch the music TV ranking show released every Sunday afternoon. Each week it presents the same songs and lists their popularity chart based on votes.

One Sunday, Michael played with his friends for too long and missed the new chart. He was very disappointed, but soon he realized that next week he could at least partially reconstruct the chart. In addition to each song’s position, the chart also lists how its rank changed compared to last week; more precisely, starting this week, for each song there is a note indicating whether it stayed in place, moved up, or moved down.

Write a program that, given the current chart, helps Michael infer a possible chart from last week.

Input Format

The first line is an integer $N(1≤N≤100)$, the total number of songs on the chart.

The next $N$ blocks list the ranking information. Each block consists of two lines. In the i-th block, the first line is the name of the i-th song; the name contains at most 100 uppercase English letters. The second line contains one of the three words: UP (the song’s position goes up), DOWN (the song’s position goes down), or SAME (no change), indicating the change compared to last week’s chart.

Output Format

Output $N$ lines: a possible chart from last week.

Each line contains one song name, that is, the $i$-th line contains the name of the song that was $i$-th on last week’s chart.

Note: The solution does not have to be unique, but for every testdata there is at least one solution.

5
HIGHHOPES
UP
LOWFEELINGS
UP
UPANDDOWN
DOWN
IAMSTILLSTANDING
DOWN
FOOLINGAROUND
DOWN

UPANDDOWN
IAMSTILLSTANDING
FOOLINGAROUND
HIGHHOPES
LOWFEELINGS

Hint

Translated by ChatGPT 5