【cf509C】Sums of Digits

2015年1月31日1,1961

Vasya had a strictly increasing sequence of positive integers a1, …, an. Vasya used it to build a new sequence b1, …, bn, where bi is the sum of digits of ai‘s decimal representation. Then sequence ai got lost and all that remained is sequence bi.

Vasya wonders what the numbers ai could be like. Of all the possible options he likes the one sequence with the minimum possible last number an. Help Vasya restore the initial sequence.

It is guaranteed that such a sequence always exists.

Input

The first line contains a single integer number n (1 ≤ n ≤ 300).

Next n lines contain integer numbers b1, …, bn  — the required sums of digits. All bi belong to the range 1 ≤ bi ≤ 300.

Output

Print n integer numbers, one per line — the correct option for numbers ai, 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 bi.

If there are multiple sequences with least possible number an, print any of them. Print the numbers without leading zeroes.

Sample test(s)
input

output

input

output

 

题解

贪心

若bi大于bi-1,就从低位一个个变成9,高位复制上一个答案

否则从选一位+1,低于它的位数清0,再从低位开始一个个放9,高位复制上一个答案

注意,可以构造出最终答案在340位。。

赛后突然想起来TAT 跪烂了