K-equivalence#531
Consider a set of positive integers.
Let and be two non-zero decimal digits. We say that and are -equivalent if the following condition holds:
For every n \in K, if exactly one digit in the decimal representation of is replaced with (or one is replaced with ), the resulting number is also an element of .
For example, when is the set of all integers divisible by , the digits , , and are -equivalent. Indeed, replacing with in the decimal notation of any number does not change its divisibility by .
It can be seen that -equivalence is an equivalence relation (it is reflexive, symmetric, and transitive).
You are given a finite set as a union of disjoint finite intervals of positive integers.
Your task is to determine the equivalence classes among the digits from to .
The first line contains , the number of intervals in the set (1 \leq n \leq 10\,000). Each of the next lines contains two positive integers a_i and b_i that define the interval [a_i, b_i] (i.e., the set of all positive integers between a_i and b_i, inclusive), where 1 \leq a_i \leq b_i \leq 10^{18}. Also, for from to : a_i \geq b_{i-1} + 2.
Represent each equivalence class by concatenating its elements in ascending order.
Output all equivalence classes of the digits from to , one per line, sorted lexicographically.
Example 1