/************************************************
Grundlegende Algorithmen mit Java,
http://algorithmen-und-problemloesungen.de/
Copyright @2007-2008 by Doina Logofatu
************************************************/

import java.io.*;
import java.util.*;

public class P05HuffmanCode {
  private static final String FileInputName = "huffman.in";
  private static final String FileOutputName = "huffman.out";

  public static void main(String[] args) throws IOException {
    Scanner scanner = null;
    PrintStream out = null;
    try {
      scanner = new Scanner(new File(FileInputName));
      TreeMap<Integer, List<Node>> map = new TreeMap<Integer, List<Node>>();
      while (scanner.hasNext()) {
        String s = scanner.next();
        if (!scanner.hasNextInt()) {
          break;
        }
        Integer cost = new Integer(scanner.nextInt());
        List<Node> list = map.get(cost);
        if (list == null) {
          list = new ArrayList<Node>();
          map.put(cost, list);
        }
        list.add(new Node(cost, s.charAt(0)));
      }

      if (map.isEmpty())
        return;
      while (map.size() > 1) {
        Iterator<Map.Entry<Integer, List<Node>>> 
                                   it = map.entrySet().iterator();
        Map.Entry<Integer, List<Node>> entry = it.next();
        ListIterator<Node> listIt = entry.getValue().listIterator();
        Node first = listIt.next();
        listIt.remove();
        if (!listIt.hasNext() && !listIt.hasPrevious()) {
          it.remove();
          entry = it.next();
          listIt = entry.getValue().listIterator();
        }
        Node second = listIt.next();
        listIt.remove();
        if (!listIt.hasNext() && !listIt.hasPrevious()) {
          it.remove();
        }
        Node newNode = new Node(first, second);
        List<Node> list = map.get(newNode.getCost());
        if (list == null) {
          list = new ArrayList<Node>();
          map.put(newNode.getCost(), list);
        }
        list.add(newNode);
      }
      out = new PrintStream(new File(FileOutputName));
      map.entrySet().iterator().next().getValue().
       iterator().next().writeCosts(
          out, new ArrayList<Boolean>());
    } finally {
      if (scanner != null) {
        scanner.close();
      }
      if (out != null) {
        out.close();
      }
    }
  }
}

class Node implements Comparable<Node> {
  private int cost;
  private char ch;
  Node left, right;

  Node(int cost, char ch) {
    this.cost = cost;
    this.ch = ch;
  }

  Node(Node left, Node right) {
    this.left = left;
    this.right = right;
    this.cost = left.cost + right.cost;
  }

  int getCost() {
    return cost;
  }

  public int compareTo(Node o) {
    return this.cost - o.cost;
  }

  void writeCosts(PrintStream out, List<Boolean> pathPrefix) {
    if (left == null || right == null) {  // leaf node
      out.print(this.ch);
      out.print('\t');
      for (Boolean b : pathPrefix) {
        out.print(b.booleanValue() ? 1 : 0);
      }
      out.println();
    } else {
      pathPrefix.add(Boolean.FALSE);
      left.writeCosts(out, pathPrefix);
      pathPrefix.set(pathPrefix.size() - 1, Boolean.TRUE);
      right.writeCosts(out, pathPrefix);
      pathPrefix.remove(pathPrefix.size() - 1);
    }
  }
}