#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<string>
#include<algorithm>
#define FOR(i,a,b) for(i=(a);i<=(b);i++)
#define ROF(i,a,b) for(i=(a);i>=(b);i--)
#define mmt(a,b) memset(a,b,sizeof(a))
#define pb push_back
#define mp make_pair
#define N 200010
#define hash Hash
#define link Link
using namespace std;
typedef long long LL;
typedef long double LD;
struct dat{LL x,y;}b[N],a[N];
struct dat2{LL x;int p,s;}c[N];
bool v[10],g[10][10];
int f[N][10],n,k,link;
map<int,int> hash;
bool cmp(dat2 a,dat2 b){return a.x<b.x;}
void change(dat2 a){a.s?b[a.p].y--:b[a.p].x--;}
void build(int v[10])
{
  int i,j;
  FOR(i,1,9) FOR(j,1,9) 
   if (v[i]&&!v[j]&&g[i][j]) g[i][j]=g[j][i]=0,link-=2;
}
void solve0()
{
  LL la;int i,j;
  la=-1;mmt(f[0],0);
  FOR(i,1,n)
  {
    int l=a[i].x%10,r=a[i].y%10;
    LL L=a[i].x/10,R=a[i].y/10;
    if (L!=la&&la>0) build(f[0]),mmt(f[0],0);
    if (L!=R)
    {
      FOR(j,l,9) f[0][j]++;
      build(f[0]);mmt(f[0],0);
      FOR(j,1,r-1) f[0][j]++;
    }else FOR(j,l,r-1) f[0][j]++;
    la=R;
  }
  build(f[0]);
}
bool solve(int k)
{
  int l,r,m=0,i,j,tot=0,p,q;LL la,L,R,Pow=1;mmt(f,0);
  FOR(i,1,k) Pow*=10;
  FOR(i,1,n)
  {
    L=a[i].x/Pow,R=a[i].y/Pow;
    if (!L&&!R) continue;
    l=a[i].x%Pow,r=a[i].y%Pow;
    b[++m].x=L+1;b[m].y=R+1;
    c[++tot].x=l;c[tot].p=m;c[tot].s=0;
    c[++tot].x=r;c[tot].p=m;c[tot].s=1;
  }
  if (!m) return 0;
  sort(c+1,c+1+tot,cmp);
  for(p=1;p<=tot&&!c[p].x;p++) change(c[p]);
  hash.clear();
  la=-1;int idx=1;
  FOR(i,1,m)
  {
    L=b[i].x/10,R=b[i].y/10;
    l=b[i].x%10,r=b[i].y%10;
    if (L!=la&&la>0) hash[la]=idx++;
    if (L!=R) 
    {
      FOR(j,l,9) f[idx][j]++;
      hash[L]=idx++;
      FOR(j,1,r-1) f[idx][j]++;
    }else FOR(j,l,r-1) f[idx][j]++;
    la=R;
  }
  hash[la]=idx++;
  FOR(i,1,idx-1) build(f[i]);
  for(;p<=tot;p=q)
  {
    for(q=p;q<=tot&&c[q].x==c[p].x;q++)
    {
      change(c[q]);
      la=c[q].s?b[c[q].p].y:b[c[q].p].x;
      k=la%10,la/=10;
      if (!hash[la]) hash[la]=idx++;
      int cur=hash[la];
      if (c[q].s) f[cur][k]--;else f[cur][k]++;
    }
    FOR(i,1,idx-1) build(f[i]);
  }
  return 1;
}
int main()
{
  ios::sync_with_stdio(false);
  scanf("%d%d",&n,&k);int i,j;
  FOR(i,1,n) scanf("%lld%lld",&a[i].x,&a[i].y),a[i].y++;
  link=72;mmt(g,1);
  solve0();
  for(i=1;i<k&&solve(i)&&link;i++);
  FOR(i,1,9)
   if (!v[i])
   {
     printf("%d",i);v[i]=1;
     FOR(j,1,9) if (!v[j]&&g[i][j]) printf("%d",j),v[j]=1;
     printf("\n");
   }
  return 0;
}