题目描述

经过一番周折，精英队伍的队员们终于来到了关押 applepi 的牢狱面前。心中神一般的领袖 applepi 就在眼前，队员们都不由自主地跪烂膝盖……不过令他们沮丧的是，牢狱的大锁没有钥匙孔，黑魔法师Vani根本就没有指望它再被打开。幸好队员们携带了新研制的终极武器——k 型氙激光器（Xenon Laser-k，代号 XLk），可以用来破拆这把锁。不过作为一道终极武器，它的启用规则异常严格。 Xenon Laser-k 上共有 $n$ 个波段能够发射激光，每个波段可以用一个闭区间 $[a_i,b_i]$ 来表示，其中 $a_i,b_i$ 为正整数，$b_{i-1}<a_i\leq b_i$。对于两个数字 $p$ 和 $q$，如果对于这 $n$ 个波段内的任意一个整数 $num$，把它在十进制表示下的后 $k$ 位中某一位上的 $p$ 换成 $q$（或者 $q$ 换成 $p$），都满足得到的整数仍然在这 $n$ 个波段内，那么称在该激光器中，数字 $p$ 和 $q$ 是 $k$ 等价的。我们称两两之间k等价的数字组成一个 $k$ 等价类。

激光器附带了 $9$ 个发射匣，代表 $1-9$ 这 $9$ 个数字。只有把同一个等价类的数字对应的发射匣安置在一排上，Xenon Laser - k 才能够启动。给定 $n$ 个波段，现在就请你求出 $1-9$ 这 $9$ 个数字分成了哪些等价类，并且每行输出一个等价类。

本题描述比较抽象，请参考样例解释。

输入格式

第一行两个整数 $n$ ， $k$。

接下来 $n$ 行每行两个整数 $a_i,b_i$。$a_i,b_i$ 为正整数，满足 $b_{i-1}<a_i\leq b_i$。

输出格式

每行一个等价类，各行之内都按照数字从小到大排序，数字中间没有空格，行与行之间按照等价类中最小的数字从小到大排序。具体格式参考样例。

样例输入 #1

1 1
1 566

样例输出 #1

123456
789

样例输入 #2

1 2
30 75

样例输出 #2

12
345
6
7
89

提示

第一个样例中，只允许修改个位。对于 $1-559$ 这些数，个位无论如何修改都在波段内。对于 $560-566$ 这些数，个位修改为大于等于 $7$ 的数字时（例如 $562$ 的 $2$ 修改为 $8$），就不在波段内了。因此 $1-6$ 和 $7-9$ 属于不同的等价类。

第二个样例每一位上都可以修改。修改方法与上面一个样例类似。

数据规模与约定

对于 $25\%$ 的数据，$1\leq n\leq 50$，$1\leq a_i\leq b_i\leq 6\times 10^3$。

对于另 $25\%$ 的数据，$n=1$。

对于另 $30\%$ 的数据，$k=1$。

对于 $100\%$ 的数据，$1\leq n\leq 1\times 10^4$，$1\leq k\leq 19$，$1\leq a_i\leq b_i\leq 10^{18}$。

在所有的数据中，均匀分布着 $25\%$ 的随机数据。

题目来源

Poetize1