# 1321.py

def codalbin (a,codifica=''):
  (sin,des)=a; cs=codifica+'0'; cd=codifica+'1'
  if isinstance(sin,list): u=codalbin(sin,cs)
  else: u={sin:cs}
  if isinstance(des,list): v=codalbin(des,cd)
  else: v={des:cd}
  u.update(v); return u

#######################################

import copy

def huffman (a):
  n=len(a)
  if n==0: return None
  if n==1: return {a[0][0]:'0'}
  if n==2: return {a[0][0]:'0', a[1][0]:'1'}
  a=copy.deepcopy(a)
  a.sort(key=lambda x: x[1], reverse=1)
  while n>2:
    v=a.pop(); u=a.pop(); peso=u[1]+v[1]; u=[[u[0],v[0]],peso]
    for i in range(0,n-2):
      if peso>a[i][1]: a.insert(i,u); break
    else: a.insert(n-2,u)
    n-=1
  a=[a[0][0],a[1][0]]; return codalbin(a)

a=[['a',30],['b',20],['c',10],['d',8],['e',6],['f',7],['g',9],['h',10]]

cod=huffman(a)
for x in sorted(cod): print (x,cod[x])