07/04/2025 01:14:52

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

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

1295. K-equivalence

Ограничения: время – 4s/8s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

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.

Input

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$ .

Output

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.

Sample Input 1

1
1 566

Sample Output 1

Sample Input 2

1
30 75

Sample Output 2