#include <stdio.h>

typedef struct _node {
   int element;
   struct _node *sublist;
   struct _node *next;
} node;

typedef node *nlist;

nlist init ()
{
   nlist L;

   L = (node *)malloc(sizeof(node));
   L -> element = 0;
   L -> sublist = NULL;
   L -> next = NULL;
   return L;
}

int isEmpty ( nlist L )
{
   return (L -> next == NULL);
}

nlist insertInt ( nlist L, int a, int k)
{
   node *p, *M;
   int i;

   p = L; i = 0;
   while ((i < k) && (p -> next != NULL)) {
      p = p -> next;
      ++i;
   }
   if (i < k) {
      fprintf(stderr,"Error in insertInt : invalid index\n");
      return L;
   }
   M = (node *)malloc(sizeof(node));
   M -> element = a;
   M -> sublist = NULL;
   M -> next = p -> next;
   p -> next = M;
   return L;
}

nlist insertList ( nlist L, nlist L1, int k)
{
   node *p, *M;
   int i;

   p = L; i = 0;
   while ((i < k) && (p -> next != NULL)) {
      p = p -> next;
      ++i;
   }
   if (i < k) {
      fprintf(stderr,"Error in insertList : invalid index\n");
      return L;
   }
   M = (node *)malloc(sizeof(node));
   M -> element = 0;
   M -> sublist = L1;
   M -> next = p -> next;
   p -> next = M;
   return L;
}

nlist join ( nlist L , nlist M )
{
   node *p;

   p = L;
   while (p -> next != NULL) p = p -> next;
   p -> next = M -> next;
   return L;
}

nlist delete ( nlist L , int k )
{
   node *p;
   int i;

   p = L; i = 0;
   while ((i < k) && (p -> next != NULL)) {
      p = p -> next;
      ++i;
   }
   if (i < k) {
      fprintf(stderr,"Error in delete : invalid index\n");
      return L;
   }
   p -> next = p -> next -> next;
   return L;
}

int print ( nlist L )
{
   node *p;

   printf("(");
   p = L -> next;
   while (p != NULL) {
      if (p -> sublist == NULL) printf("%d", p -> element);
      else print(p -> sublist);
      p = p -> next;
      if (p != NULL) printf(" ");
   }
   printf(")");
}

int main ()
{
   nlist L, L1, L2;
   int i;

   printf("*******************************************************************\n");
   printf("Generating list (1 (2) (3) (4 5))\n");
   printf("L  = init();              "); L = init(); printf("Now the list  L is "); print(L); printf("\n");
   printf("L  = insertInt(L,1,0);    "); L = insertInt(L,1,0);; printf("Now the list  L is "); print(L); printf("\n");
   printf("L1 = init();              "); L1 = init(); printf("Now the list L1 is "); print(L1); printf("\n");
   printf("L1 = insertInt(L1,2,0);   "); L1 = insertInt(L1,2,0);; printf("Now the list L1 is "); print(L1); printf("\n");
   printf("L2 = init();              "); L2 = init(); printf("Now the list L2 is "); print(L2); printf("\n");
   printf("L2 = insertInt(L2,3,0);   "); L2 = insertInt(L2,3,0);; printf("Now the list L2 is "); print(L2); printf("\n");
   printf("L  = insertList(L,L1,1);  "); L = insertList(L,L1,1); printf("Now the list  L is "); print(L); printf("\n");
   printf("L  = insertList(L,L2,2);  "); L = insertList(L,L2,2); printf("Now the list  L is "); print(L); printf("\n");
   printf("L1 = init();              "); L1 = init(); printf("Now the list L1 is "); print(L1); printf("\n");
   printf("L1 = insertInt(L1,5,0);   "); L1 = insertInt(L1,5,0);; printf("Now the list L1 is "); print(L1); printf("\n");
   printf("L1 = insertInt(L1,4,0);   "); L1 = insertInt(L1,4,0);; printf("Now the list L1 is "); print(L1); printf("\n");
   printf("L2 = init();              "); L2 = init(); printf("Now the list L2 is "); print(L2); printf("\n");
   printf("L2 = insertList(L2,L1,0); "); L2 = insertList(L2,L1,0); printf("Now the list L2 is "); print(L2); printf("\n");
   printf("L  = join(L,L2);          "); L = join(L,L2); printf("Now the list  L is "); print(L); printf("\n");

   printf("*******************************************************************\n");
   printf("Generating list (0 (1 (2 (3 (4 (5 (6)))))))\n");
   printf("L  = init();              "); L = init(); printf("Now the list  L is "); print(L); printf("\n");
   printf("L  = insertInt(L,6,0);    "); L = insertInt(L,6,0); printf("Now the list  L is "); print(L); printf("\n");
   for (i=5; i>=0; --i) {
      printf("L1 = init();              "); L1 = init(); printf("Now the list L1 is "); print(L1); printf("\n");
      printf("L1 = insertInt(L1,i,0);   "); L1 = insertInt(L1,i,0);; printf("Now the list L1 is "); print(L1); printf("\n");
      printf("L1 = insertList(L1,L,1);  "); L1 = insertList(L1,L,1); printf("Now the list L1 is "); print(L1); printf("\n");
      printf("L  = init();              "); L = init(); printf("Now the list  L is "); print(L); printf("\n");
      printf("L  = join(L,L1);          "); L = join(L,L1); printf("Now the list  L is "); print(L); printf("\n");
   }
}