eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

K-equivalence

K-equivalence

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Consider a set K of positive integers.

Let p and q be two non-zero decimal digits. Call them K-equivalent if the following condition applies:

For every n 2 K, if you replace one digit p with q or one digit q with p in the decimal notation of n then the resulting number will be an element of K.

For example, when K is the set of integers divisible by 3, the digits 1, 4, and 7 are K-equivalent. Indeed, replacing a 1 with a 4 in the decimal notation of a number never changes its divisibility by 3.

It can be seen that K-equivalence is an equivalence relation (it is reflexive, symmetric and transitive).

You are given a finite set K in form of a union of disjoint finite intervals of positive integers.

Your task is to find the equivalence classes of digits 1 to 9.

Входные данные

The first line contains n, the number of intervals composing the set K (1 ≤ n 10 000). Each of the next n lines contains two positive integers a_i and b_i that describe the interval [a_i, b_i] (i. e. the set of positive integers between a_i and b_i, inclusive), where 1 ≤ a_i b_i 10^18. Also, for i [2..n]: a_i ¸ b_{i–}_1 + 2.

Выходные данные

Represent each equivalence class as a concatenation of its elements, in ascending order.

Output all the equivalence classes of digits 1 to 9, one at a line, sorted lexicographically.

Пример

Входные данные #1
1
1 566
Выходные данные #1
1234
5
6
789
Автор Mikhail Dvorkin