Climbing Routes

Osnovne informacije

Omejitve
  • Čas: 4 s
  • Spomin: 128 MB
Avtor:
  • Vid Kocijan
  • UPM 2018

Pošlji rešitev



Tvoji rezultati.
Nisi poslal še nobene rešitve.
Več »

There are many climbing ratings used to grade the difficulty of climbing routes – one of these is the International Climbing and Mountaineering Federation (UIAA) rating. Every climbing route is assigned a Roman numeral from \mathrm{I} to \mathrm{XII}. As it turns out, such a rating is not precise enough, and a + or a - can be added to the numeral, when the route is a little harder or easier than the typical route graded with the numeral. A route of grade \mathrm{IV}\!\!+ is easier than a route of grade \mathrm{V}\!\!-, which is easier than one with a grade \mathrm{V}, which is in turn easier than a route of grade \mathrm{V}\!\!+. We are given a list of routes and their grades and we would like to order them by difficulty.

Task

There will be n routes and their difficulty grades. They need to be ordered from the easiest to the hardest, by the rating described above. The routes of the same difficulty should be ordered alphabetically by name.

For those not familiar with the Roman numerals, we list the numerals from \mathrm{I} to \mathrm{XII}:

I, II, III, IV, V, VI, VII, VIII, IX, X, XI, XII

Input

The first line contains the number of routes n. The following n lines contain the route descriptions. Each line contains the name of the climbing route and its grade, separated by a space.

Input limits

  • 1 \leq n \leq 100
  • The name length is at most 100 characters.
  • The route names are written using only the small letters of the English alphabet.
  • The grades are always Roman numerals from \mathrm{I} to \mathrm{XII}, optionally decorated with a "+" or "-" character. The Roman numerals are written using the capital letters of the English alphabet.

Output

Output n lines – the climbing routes ordered by difficulty. Only output the names, not also the grades.

Example

Input

5
nemska IV-
bavarska IV+
slovenska III
sfinga VII
ljubljanska VII-

Output

slovenska
nemska
bavarska
ljubljanska
sfinga
Tip: Log in to
  • submit and test your solution
  • post or read questions and answers about this task