Combinações de Letras

Dada uma string s que contém dígitos de 2 a 9 inclusive, escreva um programa para devolver todas as possíveis combinações de letras que o número pode representar, de acordo com o mapeamento de dígitos para letras de um teclado de telefone (imagem abaixo). As combinações de letras devem ser apresentadas em ordem lexicográfica.

Entrada

A entrada consiste numa única linha contendo a string s (1 ≤ |s| ≤ 10), em que |s| representa o comprimento da string. A string s é composta por dígitos de 2 a 9 inclusive.

Saída

Apresente todas as combinações de letras possíveis formadas pela string s, com cada combinação numa linha separada. As combinações de letras devem surgir em ordem lexicográfica.

Exemplos