#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>
#include <stdint.h>
#include <assert.h>

// LZW avec comme alphabet d'arrivé
// [0; 2^16-1], c'est-à-dire 2 octets

struct str {
  int len;
  unsigned char * data;
};

void affiche_str(struct str s){
  for (int i = 0; i < s.len; i = i + 1)
    printf("%c", s.data[i]);
}

struct str cat(struct str s, unsigned char a){
  // concaténation d'une chaîne avec un char
  struct str v;
  v.len = s.len + 1;
  v.data = malloc(v.len * sizeof(unsigned char));
  for (int i = 0; i < s.len; i = i + 1)
    v.data[i] = s.data[i];
  v.data[s.len] = a;
  return v;
}

int main(int argc, char * argv[]){
  /* Définition de variables */
  struct str dict[256*256];
  struct str epsilon = {.len = 0, .data = NULL};
  for (int i = 0; i < 256; i = i + 1)
    dict[i] = cat(epsilon, i);
  int taille_dict = 256;

  unsigned char c1, c2;
  // 1er code à gérer à part
  scanf("%c%c", &c1, &c2);
  int prev = c1 * 256 + c2;
  affiche_str(dict[prev]);
  while(scanf("%c%c", &c1, &c2) != EOF){
    int code = c1 * 256 + c2; // Code actuel
    if (taille_dict < 256 * 256){ // Encore de la place
      if (code == taille_dict)
        dict[taille_dict] = cat(dict[prev], dict[prev].data[0]);
      else
        dict[taille_dict] = cat(dict[prev], dict[code].data[0]);
      taille_dict = taille_dict + 1;
    }
    affiche_str(dict[code]);
    // Mise à jour prev
    prev = code;
  }

  for (int i = 0; i < taille_dict; i = i + 1)
    free(dict[i].data);

  return EXIT_SUCCESS;
}