题目描述

经过一番周折，精英队伍的队员们终于来到了关押 $\red{applepi }$的牢狱面前。心中神一般的 领袖 $\red{applepi }$就在眼前，队员们都不由自主地跪烂膝盖......不过令他们沮丧的是，牢狱的大 锁没有钥匙孔，黑魔法师 $\red{Vani }$根本就没有指望它再被打开。幸好队员们携带了新研制的终 极武器$\red{--k }$型氙激光器（$\red{Xenon Laser - k，}$代号 $\red{XLk}$），可以用来破拆这把锁。不过作为一 道终极武器，它的启用规则异常严格。

$\red{Xenon Laser - k }$上共有$\red{N}$个波段能够发射激光，每个波段可以用一个闭区间$\red{[a_i,b_i]}$来表示，其中$\red{a_i,b_i}$为正整数，$\red{b_{i-1}<a_i<=b_i}$。对于两个数字$\red{p}$和$\red{q，}$如果对于这$\red{N}$个波段内的任意一个整数$\red{num，}$把它在十进制表示下的后$\red{k}$ 位中某一位上的$\red{p}$换成$\red{q（}$或者$\red{q}$换成$\red{p}$），都满足得到的整数仍然在这$\red{N}$个波段内，那么称在该激光器中，数字$\red{p}$和$\red{q}$是$\red{k}$等价的。我们称两两之间$\red{k}$等价的数字组成一个$\red{k}$等价类。

激光器附带了 $\red{9 }$个发射匣，代表 $\red{1 \sim 9 }$这 $\red{9 }$个数字。只有把同一个等价类的数字对应的发射匣安置在一排上，$\red{Xenon Laser - k }$才能够启动。给定$\red{N}$个波段，现在就请你求出 $\red{1 \sim 9 }$这 $\red{9}$ 个数字分成了哪些等价类，并且每行输出一个等价类。 本题描述比较抽象，请参考样例解释。

输入格式

第一行两个整数$\red{N , k }$。

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

输出格式

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

样例

输入样例1

1 1
1 566

输出样例1

123456
789

输入样例2

1 2
30 75

输出样例2

12
345
6
7
89

提示

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

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

数据范围与约定

对于 $\red{25\% }$的数据，$\red{1<=n<=50,1<=a_i<=b_i<=6000}$。

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

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

对于 $\red{100\% }$的数据，$\red{1<=n<=10000,a<=k<=19,1<=a_i<=b_i<=10_{18}}$。

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