Pku3872 K-equivalence

对于正整数集合 $K$，非零十进制数字 $p$、$q$ 被称为 $K$-等价，当且仅当满足以下条件：

• 对于任意 $n\in K$，将 $n$ 的十进制表示中任意一个等于 $p$ 的数位单独替换为 $q$，其余数位不变，所得结果仍属于集合 $K$；
• 对于任意 $n\in K$，将 $n$ 的十进制表示中任意一个等于 $q$ 的数位单独替换为 $p$，其余数位不变，所得结果仍属于集合 $K$。

例如，若 $K$ 是所有能被 $3$ 整除的正整数构成的集合，那么数字 $1$、$4$、$7$ 两两 $K$-等价。

可以证明，$K$-等价是一种等价关系，即它满足自反性、对称性和传递性。

给定一个有限集合 $K$，请找出数字 $1$ 到 $9$ 的所有等价类。也就是说，需要将集合 $[1,9]$ 划分为若干个互不相交的子集，使得每个子集中的数字两两 $K$-等价，而属于不同子集的任意两个数字均不 $K$-等价。

输入格式

第一行输入一个整数 $n$。

接下来 $n$ 行，第 $i$ 行输入两个整数 $L_i$、$R_i$。集合 $K$ 恰为这些闭区间所覆盖的正整数的并，即

$$K=\left(\bigcup_{i=1}^{n}[L_i,R_i]\right)\cap\mathbb Z_{>0}.$$

所有区间按递增顺序给出。

输出格式

输出集合 $[1,9]$ 的所有等价类。

每个等价类用一串递增排列的数字表示，每行输出一个等价类。所有等价类按字典序输出。

样例输入

1
1 566

样例输出

1234
5
6
789

数据范围

• $1\le n\le 10^4$；
• $0\le L_i\le R_i\le 10^{18}$；
• 对于 $2\le i\le n$，满足 $L_i>R_{i-1}$。

来源与许可

本题题面与测试数据整理自 BZOJ。

样例 1

输入

1
1 566

输出

1234
5
6
789