Таблицы выставления счетов
В мире телекоммуникаций звонки на разные телефонные номера тарифицируются по различным тарифам или тарифным планам. Международный оператор связи (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"), то вывод должен содержать только число ноль.