#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct Lib_node {
  void *data;
  struct Lib_node *left, *right;
};

void lib_init_list(struct Lib_node **root)
{
  *root = NULL;
}

void *lib_add_list(struct Lib_node **root, void *data, int (*cmp)(void *, void *))
{
  int c;
  struct Lib_node *node;

  if (*root == NULL) {
    if((node = malloc(sizeof(struct Lib_node))) == NULL) {
      fprintf(stderr, "cannot allocate enoutgh memory.\n");
      exit(-1);
    }
    node->data = data;
    node->left = node->right = NULL;
    *root = node;
    return data;
  }
  if ((c = (*cmp)(data, (*root)->data)) < 0) {
    return lib_add_list(&((*root)->left), data, cmp);
  } else if (c > 0) {
    return lib_add_list(&((*root)->right), data, cmp);
  } else {
    return (*root)->data;
  }
}

void *lib_delmin_list(struct Lib_node **root)
{
  void *data;
  struct Lib_node *p;

  if (*root == NULL)
    return NULL;
  if ((*root)->left != NULL)
    return lib_delmin_list(&((*root)->left));
  data = (*root)->data;
  p = *root;
  *root = p->right;
  free(p);
  return data;
}

struct wordpack {
  char *string;
  int wc;
  struct Lib_node *root;
};

struct appearpack {
  int line;
  int word;
};

int cmp0(struct appearpack *a, struct appearpack *b)
{
  return 1;
}

int cmp1(struct wordpack *a, struct wordpack *b)
{
  return strcmp(a->string, b->string);
}

int cmp2(struct wordpack *a, struct wordpack *b)
{
  if (a->wc > b->wc)
    return -1;
  else if (a->wc < b->wc)
    return 1;
  else
    return strcmp(a->string, b->string);
}

void regword(struct Lib_node **root, char *buff, int line, int word)
{
  char *s;
  struct wordpack *wp, *data;
  struct appearpack *ap;

  if ((s = malloc(strlen(buff) + 1)) == NULL) {
    fprintf(stderr, "cannot allocate an enough memory, aborted.\n");
    exit(-1);
  }
  strcpy(s, buff);
  if ((wp = malloc(sizeof(struct wordpack))) == NULL) {
    fprintf(stderr, "cannot allocate an enough memory, aborted.\n");
    exit(-1);
  }
  wp->string = s;
  wp->wc = 0;
  lib_init_list(&(wp->root));
  data = lib_add_list(root, wp, (int (*)(void *, void *))cmp1);  
  if (data != wp) {
    free(wp->string);
    free(wp);
  }
  data->wc++;  

  if ((ap = malloc(sizeof(struct appearpack))) == NULL) {
    fprintf(stderr, "cannot allocate an enough memory, aborted.\n");
    exit(-1);
  }
  ap->line = line;
  ap->word = word;
  lib_add_list(&(data->root), ap, (int (*)(void *, void *))cmp0);  
}

void output1(struct Lib_node **root1, struct Lib_node **root2)
{
  struct wordpack *wp;
  struct appearpack *ap;
  struct Lib_node *tmp_root;
  while ((wp = lib_delmin_list(root1)) != NULL) {
    printf("%s(%d) ", wp->string, wp->wc);
    lib_init_list(&tmp_root);
    while ((ap = lib_delmin_list(&(wp->root))) != NULL) {
      printf("L%d-%d ", ap->line, ap->word);
      lib_add_list(&tmp_root, ap, (int (*)(void *, void *))cmp0);
    }
    putchar('\n');
    wp->root = tmp_root;
    lib_add_list(root2, wp, (int (*)(void *, void *))cmp2);
  }
}

void output2(struct Lib_node **root)
{
  struct wordpack *wp;
  struct appearpack *ap;
  while ((wp = lib_delmin_list(root)) != NULL) {
    printf("%s(%d) ", wp->string, wp->wc);
    while ((ap = lib_delmin_list(&(wp->root))) != NULL) {
      printf("L%d-%d ", ap->line, ap->word);
      free(ap);
    }
    putchar('\n');
    free(wp->string);
    free(wp);
  }
}

void regline(struct Lib_node **root1, char *buff, int line)
{
  char *p, *q;
  int flag, word;

  word = flag = 0;
  p = q = buff;
  for(;;) {
    if (*p == '\0') {
      if (flag > 0) {
        regword(root1, q, line, word);
      }
      break;
    }
    if ((*p >= '0' && *p <= '9') || (*p >= 'A' && *p <= 'Z') || (*p >= 'a' && *p <= 'z') || (*p == '_')) {
      if (flag == 0) {
        word++;
        flag = 1;
        q = p;
      }
    } else {
      if (flag > 0) {
        *p = '\0';
        regword(root1, q, line, word);
        flag = 0;
      }
    }
    p++;
  }
}

#define BUFFSIZE 1024 /* >= 2 */
char *getline(FILE *fp)
{
  static char inbuff[BUFFSIZE];
  char *outbuff_malloc, *tmpbuff;
  char *p, *q;
  int fEOL;
  if ((outbuff_malloc = malloc(1)) == NULL)
    return NULL;
  *outbuff_malloc = '\0';
  fEOL = 0;
  do {
    if ((q = fgets(inbuff, BUFFSIZE, fp)) == NULL)
      break;
    for (p = inbuff; *p != '\0'; p++)
      ;
    if (*(p - 1) == '\n') {
      *(p - 1) = '\0';
      fEOL = 1;
    }
    if ((tmpbuff = realloc(outbuff_malloc, strlen(outbuff_malloc) + strlen(inbuff) + 1)) ==NULL) {
      free(outbuff_malloc);
      return NULL;
    }
    strcat(tmpbuff, inbuff);
    outbuff_malloc = tmpbuff;
  } while (!fEOL);
  if (q == NULL) {
    free(outbuff_malloc);
    return NULL;
  }
  return outbuff_malloc;
}

int main(int argc, char *argv[])
{
  char *inputLine_malloc;
  FILE *fp;
  int line;
  struct Lib_node *root1, *root2;
  
  if (argc != 2) {
    fprintf(stderr, "usage: %s <file>\n", argv[0]);
    return -1;
  }
  if ((fp = fopen(argv[1], "r")) == NULL) {
    fprintf(stderr, "cannot open the file '%s'.\n", argv[1]);
    return -1;
  }
  
  lib_init_list(&root1);
  lib_init_list(&root2);
  line = 0;
  while ((inputLine_malloc = getline(fp)) != NULL) {
    line++;
    regline(&root1, inputLine_malloc, line);
    free(inputLine_malloc); /* NULL ok */
  }
  output1(&root1, &root2);
  putchar('\n');
  output2(&root2);
  fclose(fp);
  return 0;
}
/* end */