Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

C. Sums of Digits

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputVasya 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.

Input

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.

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.

Examples

Input

3

1

2

3

Output

1

2

3

Input

3

3

2

1

Output

3

11

100

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/12/2020 02:00:01 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|