Історія Правителів Сітхів#6049
Як археолог, що досліджує історію правителів Сітхів, вам часто потрібно швидко визначити, хто був при владі в певний галактичний рік. Вам надано список правителів Сітхів та роки їх правління. Напишіть програму, яка визначатиме, який правитель (або правителі) правив у зазначений рік. Зверніть увагу, що жодні два правителі ніколи не правили одночасно. Також врахуйте, що в деякі роки та місяці не було правителя, оскільки імперія була в безладі. Деякі правителі могли правити більше одного разу, але завжди з перервою, коли хтось інший був при владі.
Перший рядок вхідного файлу містить ціле число (0 < n \le 50), яке вказує кількість правителів Сітхів. Далі йдуть записів, кожен з яких описує правителя Сітхів. Перший рядок запису містить ім'я правителя, яке не перевищує символів. Другий рядок містить галактичну дату, коли правитель взяв владу, потім пробіл, а потім дату, коли він залишив владу. Обидві дати є дійсними числами, більшими за і меншими за . Друга дата завжди більша за першу. Ці числа мають одну цифру після десяткової крапки, яка представляє галактичний місяць (починаючи з ). Припускається, що правитель служить до кінця місяця, в якому залишає владу. Інший правитель ніколи не починає правити в той же місяць, коли попередній залишає владу. Мінімальний термін правління — один місяць (наприклад, правитель може правити з до , а наступний правитель почне не раніше ).
Після записів про правителів Сітхів йде ціле число (0 < c \le 50), яке вказує кількість років, що будуть перевірятися. На наступних рядках вказані галактичні роки у цілочисельному форматі. Кожен рік — це ціле число , 0 < y < 5000.
Для кожного галактичного року, зазначеного у вхідному файлі, виведіть правителя Сітхів (або правителів), які були при владі протягом цього року, у форматі, показаному в прикладі виводу. Зокрема, надрукуйте Galactic year, потім пробіл, рік, двокрапку, пробіл, а потім ім'я правителя за цей рік. Якщо протягом року було більше одного правителя, наступні правителі повинні бути перераховані з комою та пробілом перед ними. Правителі повинні бути перераховані в порядку правління від найранішого до найпізнішого в цьому році. Якщо правитель правив більше одного разу в році, його ім'я повинно бути зазначено кожного разу. Новий рядок повинен слідувати за останнім перерахованим правителем. Якщо для даного галактичного року не знайдено жодного правителя, вкажіть None після позначення галактичного року.
Приклад 1