Combinazioni di lettere

Data una stringa s che contiene cifre da 2 a 9 (incluse), scrivi un programma che restituisca tutte le possibili combinazioni di lettere che il numero potrebbe rappresentare in base alla mappatura delle cifre in lettere su una tastiera telefonica (immagine sotto). Le combinazioni di lettere devono essere stampate in ordine lessicografico.

Input

L’input consiste in un’unica riga contenente la stringa s (1 ≤ |s| ≤ 10), dove |s| rappresenta la lunghezza della stringa. La stringa s è composta da cifre comprese tra 2 e 9.

Output

Stampa tutte le possibili combinazioni di lettere che si possono formare con la stringa s, con ogni combinazione su una riga separata. Le combinazioni di lettere devono essere stampate in ordine lessicografico.

Esempi