Привіт, День зарплати!
Автоматична машина на фабриці контролює вхід та вихід працівників. Кожен працівник має електронну ідентифікаційну (ID) картку, яку потрібно вставляти в машину при вході або виході з фабрики. Машина зчитує ім'я (припустимо, S) з ID картки, а також поточну дату (припустимо, D) та час (припустимо, T) з внутрішнього таймера, і створює новий запис, позначений як D–S–T, у своїй базі даних. Час входу не раніше 8:00:00, а час виходу не пізніше 20:00:00.
На фабриці також є сторож, який завжди присутній і ретельно записує входи та виходи всіх працівників і клієнтів. Він створює окремий список кожного дня, що містить імена людей (працівників або клієнтів), які входять або виходять з фабрики протягом цього дня. Список знаходиться в тому ж порядку, в якому люди входять або виходять. Імена працівників у цьому списку точно такі ж рядки, як записані автоматичною машиною. Зверніть увагу, що клієнти не мають ID карток.
Цілком можливо, що деякі працівники забувають вставити свої ID картки в машину. Але ми припускаємо, що кожен працівник робить цю помилку не більше одного разу на день. Ми також знаємо, що кожен працівник, який приходить на роботу на фабрику в певний день, входить на фабрику рівно один раз і виходить з неї рівно один раз у цей день.
Наприкінці місяця, і в день виплати зарплати, директор фабрики зазначає, що, з інформацією, записаною автоматичною машиною та списками, підготовленими сторожем, неможливо точно визначити, скільки годин кожен працівник був присутній (працював) на фабриці протягом минулого місяця. Тому він вирішує платити кожному працівнику 100K ріалів, помножених на "середній" час, який він/вона був присутній на фабриці протягом цих днів. "Середній" час обчислюється як середнє з двох чисел: одне є мінімально можливим, а інше є максимально можливим часом, який працівник був присутній на фабриці протягом робочих днів у минулому місяці.
Вам потрібно написати програму, щоб визначити мінімальний і максимальний можливий час, який кожен працівник був присутній на фабриці.
Вхідні дані
У першому рядку вхідних даних знаходиться ціле число t (1 ≤ t ≤ 10), кількість тестових випадків, за якими слідують дані для тестових випадків. Кожен рядок тестового випадку є записом бази даних машини або звітом сторожа в кінці дня. Кожен рядок, що представляє запис машини, виглядає як D–S–T, де S - це рядок з малих літер, D - це дата, відформатована як YY/MM/DD, а T - це часовий штамп, відформатований як HH:MM:SS. У цьому типі вхідних рядків немає пробілів. Кожен рядок, що представляє звіт сторожа за один день, містить 1 ≤ k ≤ 40 імен, як у наступному прикладі:
D S_1 S_2 S_3 … S_k
Це означає, що на дату D (у форматі YY/MM/DD) перша особа на ім'я S_1 увійшла або вийшла з фабрики, потім друга особа на ім'я S_2 і так далі. Дата та імена розділені одним пробілом. У тестовому випадку не може бути більше одного рядка звіту сторожа для тієї ж дати. Період інтересу не перевищує 30 днів. Імена осіб не перевищують 15 символів, і жодні дві особи не мають однакового імені. Кожен тестовий випадок завершується рядком, що містить один символ #. У компанії є принаймні один працівник і не більше 15 працівників. Два записи машини на певну дату можуть мати однаковий часовий штамп. У цьому випадку сторож може записати відповідні події в будь-якому порядку.
Вихідні дані
Файл вихідних даних містить відповіді на тестові випадки, де i-та відповідь відповідає i-му тестовому випадку. Кожен рядок відповіді має форму:
S-H_1 M_{1 } S_1-H_{2 } M_{2 } S_2
Де S - це ім'я працівника, H_1, M_{1 }і_{ }S_{1 }представляють мінімальний час присутності працівника S протягом періоду інтересу, а H_2, M_{2 }і_{ }S_{2 }представляють те ж саме для максимального часу присутності працівника S. (H_i, M_i, і S_i вказують години, хвилини та секунди без будь-яких провідних нулів.) Рядки в кожній відповіді повинні бути відсортовані за полем S в алфавітному порядку (словниковий порядок). Кожна відповідь завершується рядком, що містить один символ #.