Pku3872 K-equivalence - Problem

Description

对于正整数集合K, 非零十进制数字p, q被称作K-等价当且仅当以下条件成立:对于所有n∈K, 如果将n中的数字p替换成数字q, 或者将n中的数字q替换成p, 得到的新数字依然属于集合K. 例如, K是所有能被3整除的数构成的集合, 那么数字1, 4, 7是K-等价的. 可以看到, K-等价是一个等价关系(它满足自反性, 对称性和传递性). 给定一个有限集合K, 你的任务是找到数字1到数字9的等价类(即将[1,9]划分为若干个不相交的子集, 使得每个子集中的元素两两K-等价, 且任意两个属于不同集合的元素不K-等价).

Input

第一行为整数n, 接下来有n行, 每行两个整数Li, Ri, 代表区间[Li, Ri]属于集合K. 0<=Li<=Ri<=1018, 且对于i>=2, Li>Ri-1.

Output

输出[1,9]的等价类. 每个等价类用一串递增的数字表示, 按照字典序输出.

Sample Input

1
1 566

Sample Output

1234
5
6
789

Hint

Source

Neerc2010

黑暗爆炸OJ

DARKBZOJ

#2224. Pku3872 K-equivalence