Letter Combinations（文字の組み合わせ）

2 から 9 までの数字のみを含む文字列 s が与えられた場合、電話のキーパッドにおける数字と文字の対応関係に基づいて、その数字が表す可能性のある文字の組み合わせをすべて求めるプログラムを作成してください（下の画像を参照）。求めた文字の組み合わせは、辞書順に出力してください。

入力

入力は 1 行で与えられ、この行に文字列 s が含まれます (1 ≤ |s| ≤ 10)。ここで |s| は文字列の長さを表します。文字列 s は 2 から 9 までの数字のみで構成されています。

出力

与えられた s から生成できるすべての文字の組み合わせを出力してください。各組み合わせは 1 行に 1 つずつ出力し、出力する際は辞書順に並べてください。

例