#include "stdio.h"
#include "conio.h"
#include "stdlib.h"
#define MAX 5
typedef struct node
{
int k;
struct node  *next;
} *lnode;

lnode my_input(int *d)
{
lnode head,temp,terminal;
char s[MAX+1];
printf("Input the records:\n");
scanf("%s",s);
head=NULL;
*d=0;
terminal=NULL;
while(s[0]!='0')
{
  temp=(lnode)malloc(sizeof(struct node));
  if (strlen(s)>*d) *d=strlen(s);
  temp->k=atoi(s);
  if (head==NULL)
  {
   head=temp;
   terminal=temp;
   }
   else
   {
    terminal->next=temp;
    terminal=temp;
    }
    scanf("%s",s);
}
    terminal->next=NULL;
    return head;
}

void my_output(lnode h)
{
printf("\n");
while (h!=NULL)
{
  printf("%d ",h->k);
  h=h->next;
  }
getch();
}


lnode bs(lnode head,int d)
{
lnode p,q,h,t;
int i,j,x,radix=1;
  h=(lnode)malloc(10*sizeof(struct node));
  t=(lnode)malloc(10*sizeof(struct node));
for (i=d;i>=1;i--)
{
  for (j=0;j<=9;j++)
  {
   h[j].next=NULL;
   t[j].next=NULL;
  }
   p=head;
   while (p!=NULL)
   {
    x=((p->k)/radix)%10;
    if (h[x].next==NULL)
     {
      h[x].next=p;
      t[x].next=p;
      }
     else
     {
      q=t[x].next;
      q->next=p;
      t[x].next=p;
      }
     p=p->next;
   }
   j=0;
   while (h[j].next==NULL)
    j++;
   head=h[j].next;
   q=t[j].next;
   for (x=j+1;x<=9;x++)
    if (h[x].next!=NULL)
     {
      q->next=h[x].next;
      q=t[x].next;
      }
  q->next=NULL;
  radix*=10;
  printf("\n---------------------\n");
}
return head;
}

void my_free(lnode h)
{
lnode temp=h;
while (temp)
{
  h=temp->next;
  free(temp);
  temp=h;
  }
}

void main()
{
lnode h;
int d;
h=my_input(&d);
h=bs(h,d);
my_output(h);
my_free(h);
}