open ExtString;; 
let (|>) x f = f x;; 
 
let iter_file_lines fname f = (* для каждой строки файла fname выполнить f *) 
  let ic = open_in fname in    
  Enum.iter f (Std.input_lines ic);  
  close_in ic;; 
   
let numerize s = (* закодировать строку цифрами, игнорируя не-буквы *) 
  let letters = "ejnqrwxdsyftamcivbkulopghz"  
  and digits  = "01112223334455666777888999" in 
  let mapper c = try String.sub digits (String.index letters c) 1 with Not_found->"" 
  in String.replace_chars mapper (String.lowercase s);; 
   
let dict = Hashtbl.create 100;; (* словарь - таблица "номер -> список кодируемых им слов" *) 
(* каждое слово из словаря помещаем в соответствующий список *) 
iter_file_lines "dictionary.txt" (fun s -> Hashtbl.add dict (numerize s) s);; 
 
(* функция find получает строку с цифрами и возвращает список слов,  
   кодировка которых является префиксом этой строки, вместе с количеством 
   цифр в кодировке каждого слова *) 
let find str = 
  Enum.init (String.length str) (fun i->String.sub str 0 (i+1)) |> 
  Enum.map (fun s->List.map (fun w-> (w, String.length (numerize w))) (Hashtbl.find_all dict s)) |> 
  Enum.fold (@) [];; 
 
(* Функция обработки одного номера. Выводит в нужном формате все его кодировки. *) 
let process phone =  
  (* для остатка строки, текущего накопленного результата и флага использования цифры *) 
  let rec encode str res dig_used =  
    (* если дошли до конца строки и есть результат, вывести его *) 
    if str = "" then (if res<>"" then Printf.printf "%s:%s\n" phone res) else 
    let vars = find str in (* иначе, найти варианты кодировки начала остатка строки *) 
    if vars = [] then (* если их нет, то, если можно, использовать цифру и продолжить *) 
      (if dig_used then () else encode (String.lchop str) (res^" "^(String.sub str 0 1))  true) 
    (* если же варианты есть, то для каждого варианта добавить его к результату и обработать 
       остаток строки *)     
    else List.iter (fun (word,k)->  
      encode (String.sub str k (String.length str - k)) (res ^ " " ^ word) false ) vars  in 
  (* убрать из номера все, кроме цифр *)   
  let digits = String.replace_chars (function '0'..'9' as c-> String.of_char c |_->"") phone in 
  encode digits "" false;;   
   
iter_file_lines "input.txt" process;; (* обработать весь входной список *)