Sums of Digits

题意翻译

定义两个序列 a 和 b。 a序列是一个由正整数构成的单调严格递增的序列。同时 b 序列中的 $b_i$ 是 $a_i$ 的各数位上的数字之和。 已知b序列，请根据b还原出a序列。同时要求 $a_n$ (a序列的最后一项)尽可能的小。 数据保证有解。 输入：第一行一个数 n ，表示 a 序列与 b 序列的长度。 接下来每行一个数，第 $i+1$ 行为$ b_i$ 的值。 输出：每行一个数，第 $i$ 行为$ a_i$ 的值。

题目描述

Vasya had a strictly increasing sequence of positive integers $ a_{1} $ , ..., $ a_{n} $ . Vasya used it to build a new sequence $ b_{1} $ , ..., $ b_{n} $ , where $ b_{i} $ is the sum of digits of $ a_{i} $ 's decimal representation. Then sequence $ a_{i} $ got lost and all that remained is sequence $ b_{i} $ . Vasya wonders what the numbers $ a_{i} $ could be like. Of all the possible options he likes the one sequence with the minimum possible last number $ a_{n} $ . Help Vasya restore the initial sequence. It is guaranteed that such a sequence always exists.

输入输出格式

输入格式

The first line contains a single integer number $ n $ ( $ 1<=n<=300 $ ). Next $ n $ lines contain integer numbers $ b_{1} $ , ..., $ b_{n} $ — the required sums of digits. All $ b_{i} $ belong to the range $ 1<=b_{i}<=300 $ .

输出格式

Print $ n $ integer numbers, one per line — the correct option for numbers $ a_{i} $ , in order of following in sequence. The sequence should be strictly increasing. The sum of digits of the $ i $ -th number should be equal to $ b_{i} $ . If there are multiple sequences with least possible number $ a_{n} $ , print any of them. Print the numbers without leading zeroes.

输入输出样例

输入样例 #1

3
1
2
3

输出样例 #1

1
2
3

输入样例 #2

3
3
2
1

输出样例 #2

3
11
100