K-эквивалентность
Рассмотрим множество K положительных целых чисел.
Пусть p и q — две ненулевые десятичные цифры. Назовем их K-эквивалентными, если выполняется следующее условие:
Для каждого n из K, если заменить одну цифру p на q или одну цифру q на p в десятичной записи n, то полученное число будет элементом K.
Например, когда K — это множество чисел, делящихся на 3, цифры 1, 4 и 7 являются K-эквивалентными. Действительно, замена 1 на 4 в десятичной записи числа никогда не изменяет его делимость на 3.
Можно заметить, что K-эквивалентность является отношением эквивалентности (оно рефлексивно, симметрично и транзитивно).
Вам дано конечное множество K в виде объединения непересекающихся конечных интервалов положительных целых чисел.
Ваша задача — найти классы эквивалентности цифр от 1 до 9.
Входные данные
Первая строка содержит n, количество интервалов, составляющих множество K (1 ≤ n ≤ 10 000). Каждая из следующих n строк содержит два положительных целых числа a_i и b_i, которые описывают интервал [a_i, b_i] (т. е. множество положительных целых чисел между a_i и b_i, включительно), где 1 ≤ a_i ≤ b_i ≤ 10^18. Также, для i [2..n]: a_i > b_i-1 + 2.
Выходные данные
Представьте каждый класс эквивалентности в виде конкатенации его элементов в порядке возрастания.
Выведите все классы эквивалентности цифр от 1 до 9, по одному на строку, отсортированные лексикографически.