Таблиці для виставлення рахунків
У світі телекомунікацій дзвінки на різні телефонні номери тарифікуються за різними тарифами або планами. Міжнародний оператор телефонних комунікацій (ICPC) має стару таблицю тарифікації, яка визначає, за яким планом має тарифікуватися кожен дзвінок.
Кожен міжнародний телефонний номер складається з 11 цифр. Таблиця тарифікації містить n рядків. Кожен рядок визначає діапазон префіксів телефонних номерів, наприклад, "7919 - 921". Це означає, що всі телефонні номери, які починаються з 7919, 7920 та 7921, відповідають цьому рядку. Для кожного префіксу вказано назву тарифного плану. Щоб визначити тарифний план для дзвінка, таблиця переглядається зверху вниз, і перший відповідний рядок визначає тарифний план. Якщо відповідності не знайдено, телефонний номер вважається недійсним, і тарифний план не потрібен. Спеціальний тарифний план з назвою "invalid" (без лапок) використовується для позначення недійсних телефонних номерів. Деякі тарифні плани застосовуються до різних телефонних номерів, і їхні назви можуть з'являтися в різних рядках таблиці.
Таблиця тарифікації ICPC стара і містить багато записів. Деякі з них можуть навіть не використовуватися. Дуже важко зрозуміти, для яких телефонних номерів фактично використовується кожен тарифний план. Керівництво ICPC вирішило перетворити цю таблицю в більш зрозумілий формат. У новому форматі таблиця складається з лексикографічно впорядкованого списку простих префіксів (без діапазонів "-") з назвою тарифного плану для кожного префіксу. Жоден префікс нової таблиці не повинен бути префіксом іншого префіксу з таблиці. Таким чином, простий пошук у словнику (наприклад, бінарний пошук) буде достатнім, щоб визначити тарифний план для даного телефонного номера. Знайти всі телефонні номери для даного тарифного плану також стане простою задачею. Кількість рядків у новій таблиці має бути мінімізована. Тарифний план з назвою "invalid" не повинен бути присутнім у новій таблиці, оскільки недійсні телефонні номери будуть позначені відсутністю відповідного префіксу в новій таблиці.
Вхідні дані
Перший рядок вхідних даних містить одне ціле число n (1 ≤ n ≤ 100) — кількість рядків у старій таблиці тарифікації. Наступні n рядків описують стару таблицю тарифікації з одним правилом у рядку. Кожне правило містить чотири токени, розділені пробілами — префікс A, знак мінус ("-"), префікс B та назву тарифного плану. Префікси містять від 1 до 11 цифр кожен, а назва тарифного плану містить від 1 до 20 малих літер.
Позначимо |A| кількість цифр у префіксі A. Вірно, що 1 ≤ |B| ≤ |A| ≤ 11. Більше того, останні |B| цифр префіксу A утворюють рядок, який лексикографічно дорівнює або передує B.
Така пара префіксів A та B відповідає всім телефонним номерам, у яких перші |A| – |B| цифр збігаються з першими цифрами A, а наступні |B| цифр є лексикографічно між останніми |B| цифрами A та B (включно).
Вихідні дані
Виведіть одне ціле число k — мінімальну кількість рядків, яку повинна містити нова таблиця, щоб описати дану стару таблицю тарифікації. Потім виведіть k рядків з лексикографічно впорядкованою новою таблицею тарифікації. Запишіть два токени, розділені пробілом у кожному рядку — префікс та назву тарифного плану. Зверніть увагу, що префікс у новій таблиці тарифікації повинен містити принаймні одну цифру.
Якщо всі телефонні номери є недійсними (кожен телефонний номер не має відповідного рядка або відповідає рядку з тарифним планом "invalid"), то вивід повинен містити лише число нуль.