У Васи была строго возрастащая последовательность целых положительных чисел a1, ..., an. Вася построил по ней новую последовательность b1, ..., bn, где bi — сумма цифр ai в десятичной записи. После этого последовательность ai потерялась, осталась только последовательность bi.
Васе интересно, какими могли быть числа ai. Из всех вариантов последовательности a ему интересен такой, в котором последнее число an является минимально возможным. Помогите Васе восстановить исходную последовательность.
Гарантируется, что подобная последовательность всегда существует.
Выходные данные
Выведите n чисел по одному на строке — корректный вариант для чисел ai, в порядке возрастания индексов. Последовательность должна быть строго возрастающей. Сумма цифр i-го числа должна быть равна bi. Если вариантов с минимальным значением последнего числа несколько, выведите любой. Числа следует выводить без ведущих нулей.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1
2
3
|
1
2
3
|
|
2
|
3
3
2
1
|
3
11
100
|