Рабочее место участника

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\ ∈\ 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 566

1234
5
6
789

1
30 75

12
345
6
7
89