#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 node {
  uint16_t code;
  struct node * fils[256];
};
typedef struct node * trie;

trie create(uint16_t code){
  trie n = malloc(sizeof(struct node));
  n -> code = code;
  for (int i = 0; i < 256; i = i + 1)
    n -> fils[i] = NULL;
  return n;
}

void free_trie(trie t){
  if (t == NULL) return;
  for (int i = 0; i < 256; i = i + 1)
    free_trie(t -> fils[i]);
  free(t);
}

void affiche_code(uint16_t code){
  //printf("Affiché : %d\n", code);
  printf("%c%c", code / 256, code % 256);
}

int main(int argc, char * argv[]){
  /* Définition de variables */
  trie dict = create(0);
  for (int i = 0; i < 256; i = i + 1)
    dict->fils[i] = create(i);
  int prochain_code = 256;

  unsigned char c;  // caractère actuel
  trie curr = dict; // noeud actuel
  while(scanf("%c", &c) != EOF){
    //printf("lu : %d\n", c);
    if (curr -> fils[c] != NULL)
      curr = curr->fils[c];
    else {
      affiche_code(curr -> code);
      if (prochain_code < 256*256){ // Il reste de la place
        curr->fils[c] = create(prochain_code);
        prochain_code = prochain_code + 1;
      }
      curr = dict -> fils[c];
    }
  }
  if (curr != dict)
    affiche_code(curr -> code);

  /* Libération de la mémoire */
  free_trie(dict);

  return EXIT_SUCCESS;
}