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: Jan/28/2020 14:49:58 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|