인기 순위 목록

매주 일요일 오후, 한 텔레비전 음악 방송은 같은 곡들을 소개하고 시청자 투표를 바탕으로 곡들의 인기 순위 목록을 보여 준다. 1번 자리가 목록의 가장 위(1위)이다.

이번 주 목록에는 각 자리마다 지금 그 자리에 있는 곡의 이름과 함께, 그 곡이 지난주 목록과 비교해 어떻게 이동했는지를 나타내는 표시가 나온다.

• UP — 그 곡이 지난주보다 더 높은(번호가 더 작은) 자리로 올라갔다.
• DOWN — 그 곡이 지난주보다 더 낮은(번호가 더 큰) 자리로 내려갔다.
• SAME — 그 곡이 지난주와 정확히 같은 자리에 있다.

지난주 목록은 보지 못했다. 이번 주 목록과 이동 표시를 이용해, 그와 모순되지 않는 지난주 목록 하나를 복원하여라.

즉, 이번 주 i번 자리에서 UP 표시가 된 곡은 지난주에 i보다 큰 번호의 자리에 있었고, DOWN 표시가 된 곡은 i보다 작은 번호의 자리에 있었으며, SAME 표시가 된 곡은 지난주에도 i번 자리에 있었다.

첫째 줄에 곡의 수 N(1 ≤ N ≤ 100)이 주어진다.

이어지는 N개의 블록이 이번 주 목록을 1번 자리부터 N번 자리까지 순서대로 나타낸다. 각 블록은 두 줄로 이루어진다.

• 그 자리에 있는 곡의 이름. 최대 100개의 영어 대문자(A–Z)로 이루어진다.
• UP, DOWN, SAME 중 한 단어로, 지난주 대비 그 곡의 이동을 나타낸다.

주어진 입력에 대해 유효한 지난주 목록이 항상 적어도 하나 존재한다. 곡 이름은 서로 다르다.

지난주 목록을 N개의 줄로 출력한다. i번째 줄에는 지난주 i번 자리에 있던 곡의 이름을 출력한다.

입력과 모순되지 않는 지난주 목록이 여러 개일 수 있다. 그중 사전순으로 가장 작은 목록을 출력하여라. 두 후보 목록을 위에서부터 한 줄씩 비교하여, 처음으로 다른 줄에서 알파벳순으로 더 작은 곡 이름을 가진 목록을 택한다.