[Nescafé 17]终极武器

成绩 0 开启时间 2013年02月21日 星期四 18:02
折扣 0.8 折扣时间 2013年02月28日 星期四 18:02
允许迟交 关闭时间 2013年02月28日 星期四 18:02
输入文件 laser.in 输出文件 laser.out

题目描述

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

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

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

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

输入格式

第一行两个整数$N$,$k$

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

输出格式

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

样例输入1

1 1
1 566

样例输出1

123456
789

样例输入2

1 2
30 75

样例输出2

12
345
6
7
89

样例说明

第一个样例中$k=1$,只允许修改个位。对于1~559这些数,个位无论如何修改都在波段内。对于560~566这些数,个位修改为大于等于7的数字时(例如5622修改为8),就不在波段内了。因此1~67~9属于不同的等价类。

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

数据范围与约定

对于25% 的数据,$1 \le n \le 50 $$1 \le a_i \le b_i \le 6000 $

对于另25% 的数据,$n=1$

对于另30% 的数据,$k=1$

对于100% 的数据,$1 \le n \le 10000 , 1 \le k \le 19 , 1 \le a_i \le b_i \le 10^{18} $

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