z1l8

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

#define SIZE 26

struct Node;
struct Node {
  int count;
  char symbol;
  struct Node *parent;
  struct Node *edges[SIZE];
} Node;

void read_data(struct Node *root) {
  int c;
  struct Node *current = root;
  while ((c = getchar()) != EOF) {
    if (c == '\n') {
      current->count++;
      current = root;
      continue;
    }
    int idx = c - 'a';
    if (current->edges[idx] == NULL) {
      current->edges[idx] = (struct Node *)calloc(sizeof(Node), 1);
      current->edges[idx]->parent = current;
      current->edges[idx]->symbol = c;
    }

    current = current->edges[idx];
  }
}

static char word[1000000];

void travel(struct Node *node) {
  while (node->count--) {
    struct Node *parent = node->parent;
    int idx = 0;

    while (parent != NULL) {
      word[idx++] = parent->symbol;
      parent = parent->parent;
    }

    while (idx--)
      putchar(word[idx]);

    printf("%c\n", node->symbol);
  }

  for (int i = 0; i < SIZE; i++) {
    struct Node *edge = node->edges[i];
    if (edge != NULL)
      travel(edge);
  }
}

int main(void) {
  struct Node *root = (struct Node *)calloc(sizeof(Node), 1);
  read_data(root);
  putchar('\n');
  travel(root);

  return 0;
}