The History of the Sith Rulers

As an archaeologist studying the history of the Sith rulers, you frequently need to look up quickly which ruler held power in a given galactic year. Given a list of Sith rulers and the periods during which each held power, write a program that prints which ruler (or rulers) governed in a specified year.

Note the following:

• No two rulers ever ruled at the same time.
• Some years and months had no ruler at all, as the empire fell into disarray.
• Some rulers led more than once, but there was always a break in their rule before they reassumed power (someone else ruled before they came back to power).

The first line of the input contains an integer $n$ ($0 < n \le 50$), the number of Sith rulers. It is followed by $n$ entries, one per ruler.

The first line of each entry contains the name of the ruler, which is at most 30 characters long. The second line of the entry contains the galactic date on which the ruler assumed power, then a single space, then the galactic date on which the ruler left power.

Both dates are real numbers greater than $0$ and less than $5000$, written with exactly one digit after the decimal point. The second date is always greater than the first. The single digit to the right of the decimal point represents a galactic month, numbered starting from $0$.

For the date on which a ruler leaves power, the ruler is assumed to serve through the end of the listed month. More precisely, no ruler ever assumes power in the same month the previous ruler leaves it. The minimum time any ruler serves is one month (so a ruler may serve from $1.1$ to $1.1$, and any ruler who follows must start no earlier than $1.2$).

After the ruler entries comes an integer $c$ ($0 < c \le 50$), the number of year queries that follow. Each of the next $c$ lines contains one galactic year as an integer $y$, with $0 < y < 5000$.

For each galactic year in the input, print the Sith ruler (or rulers) in power during that year, in the format shown in the examples.

Specifically, print Galactic year, a space, the year, a colon, a space, and then the name of the ruler for that year. If there was more than one ruler during the year, each subsequent ruler is preceded by a comma and a space (, ). The rulers must be listed in the order in which they ruled, from earliest to latest within that year. If a ruler ruled more than once in a year, that ruler is listed once for each reign. A newline immediately follows the last ruler listed.

If no ruler is found for a given galactic year, print None after the galactic year designation.