2804. K-equivalence

单点时限: 2.0 sec

内存限制: 256 MB

未加数据

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 in 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 ai and bi that describe the interval [ai, bi] (i. e. the set of positive integers between ai and bi, inclusive), where 1 <= ai <= bi <= 1018. Also, for i( 2<= i <= n ) : ai >= bi-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.

样例

Input
1
1 566
/*
1
30 75
*/
Output
1234
5
6
789
/*
12
345
6
7
89
*/

0 人解决,3 人已尝试。

0 份提交通过,共有 7 份提交。

9.9 EMB 奖励。

创建: 17 年,1 月前.

修改: 6 年,10 月前.

最后提交: 10 年,8 月前.

来源: Northeastern European Regional Contest 2009

题目标签