Vasya had a strictly increasing sequence of positive integers a₁, ..., a_n. Vasya used it to build a new sequence b₁, ..., 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.

Input

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

Next n lines contain integer numbers b₁, ..., b_n — the required sums of digits. All b_i belong to the range 1 ≤ b_i ≤ 300.

Output

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.

Sums of Digits

Examples