История правителей ситхов
Как археолог, изучающий историю правителей ситхов, вам часто необходимо быстро определить, кто был у власти в определённый галактический год. Имея список правителей ситхов и годы их правления, напишите программу, которая будет отображать, какой правитель (или правители) правил в указанный год. Учтите, что два правителя никогда не правили одновременно. Также учтите, что в некоторые годы и месяцы правителя могло не быть вовсе, так как империя была в беспорядке. Наконец, некоторые правители могли править более одного раза, но всегда с перерывом, прежде чем снова прийти к власти (кто-то другой правил между их сроками).
Входные данные
Первая строка входного файла содержит целое число n (0 < n ≤ 50), указывающее количество правителей ситхов. Далее следуют n записей, каждая из которых описывает правителя ситхов. Первая строка записи содержит имя правителя, не превышающее 30 символов. Вторая строка записи содержит галактическую дату начала правления, затем пробел, а затем дату окончания правления. Обе даты — это действительные числа больше 0 и меньше 5000. Вторая дата всегда больше первой. Эти числа указаны с одной цифрой после десятичной точки, которая обозначает галактический месяц (начиная с 0). Предполагается, что правитель всегда служит до конца указанного месяца. Более конкретно, другой правитель никогда не приходит к власти в том же месяце, когда предыдущий правитель покидает власть. Минимальное время правления составляет один месяц (например, правитель может править с 1.1 до 1.1, и следующий правитель может начать не ранее 1.2).
После записей о правителях ситхов следует целое число c (0 < c ≤ 50), указывающее количество записей о годах, которые последуют. На c строках указаны галактические годы в целочисленном формате. Каждый год — это целое число y, 0 < y < 5000.
Выходные данные
Для каждого указанного в входном файле галактического года отобразите правителя ситхов (или правителей), находившихся у власти в течение этого года, в формате, показанном в примере вывода ниже. Напечатайте "Galactic year", за которым следует пробел, затем год, затем двоеточие, затем пробел, затем имя правителя за этот год. Если в течение этого года было более одного правителя, последующие правители должны быть перечислены с запятой и пробелом перед ними. Правители должны быть перечислены в порядке правления от самого раннего до самого позднего в этом году. Если правитель правит более одного раза в году, он должен быть указан каждый раз. Новая строка должна следовать сразу после последнего указанного правителя. Если для данного галактического года не найдено правителей, укажите "None" после обозначения галактического года.