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, по одному на рядок, відсортовані лексикографічно.