Задача №1894. K-эквивалентность
Зафиксируем некоторое множество натуральных чисел \(K\). Две ненулевые десятичные цифры \(p\) и \(q\) называются \(K\)-эквивалентными, если выполнено следующее условие:
Для всех \(n\in K\), если вы замените одну какую-либо цифру \(p\) на цифру \(q\) или одну цифру \(q\) на цифру \(p\) в десятичной записи числа \(n\), то получившееся число будет лежать в \(K\). Например, если \(K\) — это множество натуральных чисел, делящихся на 3, то цифры 1, 4 и 7 являются \(K\)-эквивалентными. Очевидно, что, например, замена 1 на 4 в десятичной записи числа не меняет его остаток по модулю 3.
Ясно, что \(K\)-эквивалентность является отношением эквивалентности (очевидно, что оно рефлексивно, симметрично и транзитивно).
Вам дано конечное множество \(K\), заданное с помощью объединения непересекающихся отрезков натуральных чисел. Ваша задача — написать программу, находящую классы эквивалентности ненулевых десятичных цифр.
Первая строка содержит \(n\) — количество интервалов, составляющих множество \(K\) (\(1 \le n \le 10\,000\)).
Каждая из последующих \(n\) строк содержит два натуральных числа \(a_i\) и \(b_i\), описывающие отрезок \([a_i, b_i]\) (то есть множество натуральных чисел между \(a_i\) и \(b_i\), включительно), где \(1 \le a_i \le b_i \le 10^{18}\). Кроме того, для \(i \in [2,n]\) \(a_i \ge b_{i-1} + 2\).
Выведите для каждого класса эквивалентности одну строку — конкатенацию составляющих его элементов в порядке возрастания.
Классы эквивалентности необходимо выводить в лексикографическом порядке соответствующих строк.
1 1 566
1234 5 6 789
1 30 75
12 345 6 7 89