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.


-----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

Difficulty: interview

Starter code:

Solutions:
"""
Codeforces Contest 289 Div 2 Problem C

Author  : chaotic_iak
Language: Python 3.4.2
"""

################################################### SOLUTION

def printing(num):
    arr = num[:]
    while len(arr) > 1 and arr[-1] == 0: arr.pop()
    print("".join(map(str, reversed(arr))))

def main():
    n, = read()
    last = [0]*500
    for i in range(n):
        b, = read()
        last[0] += 1
        p = 0
        while last[p] == 10:
            last[p] = 0
            p += 1
            last[p] += 1
        p = 0
        while sum(last) > b:
            last[p] = 0
            p += 1
            k = p
            last[k] += 1
            while last[k] == 10:
                last[k] = 0
                k += 1
                last[k] += 1
        p = 0
        while sum(last) < b:
            while last[p] == 9: p += 1
            last[p] += 1
        printing(last)



#################################################### HELPERS



def read(mode=2):
    # 0: String
    # 1: List of strings
    # 2: List of integers
    inputs = input().strip()
    if mode == 0: return inputs
    if mode == 1: return inputs.split()
    if mode == 2: return list(map(int, inputs.split()))

def write(s="\n"):
    if s is None: s = ""
    if isinstance(s, list): s = " ".join(map(str, s))
    s = str(s)
    print(s, end="")

write(main())

n = int(input())

def get_sum(x):
    result = 0
    while x > 0:
        d, m = divmod(x, 10)
        result += m
        x = d
    return result

def dec(x):
    assert x != 0
    t = x
    mult = 1
    while True:
        d, m = divmod(x, 10)
        if m != 0:
            return t + (10 - m) * mult
        x = d
        mult *= 10

def get_next(prev_x, prev_sum, sum):
    t = prev_x
    while True:
        while prev_sum > sum:
            prev_x = dec(prev_x)
            prev_sum = get_sum(prev_x)
        s = list(reversed(str(prev_x)))
        required = sum - prev_sum
        i = 0
        while required:
            try:
                a = min(9 - (ord(s[i]) - ord('0')), required)
                s[i] = chr(ord(s[i]) + a)
            except IndexError:
                a = min(9, required)
                s += chr(a + ord('0'))
            required -= a
            i += 1
        x = int("".join(reversed(s)))
        if x != t:
            return x
        prev_x = dec(prev_x)
        prev_sum = get_sum(prev_x)

a = s = 0
for i in range(n):
    b = int(input())
    a = get_next(a, s, b)
    print(a)
    s = b


__author__ = 'PrimuS'

n = int(input())
b = [0] * n
for i in range(n):
    b[i] = int(input())

last = 0

import math


def build_smallest(csum, length):
    if math.ceil(csum / 9) == length:
        f = csum % 9
        if f == 0:
            f = 9
        return int(str(f) + "9" * (length-1))

    csum -= 1
    s = ""
    while csum > 0:
        s = str(min(csum, 9)) + s
        csum -= min(csum, 9)

    return int("1" + "0" * (length - 1 - len(s)) + s)


def build_greater(csum, x):
    x = [int(y) for y in x]

    last_possible = -1
    i = len(x) - 1
    while i >= 0:
        if x[i] < 9:
            last_possible = i
            break
        i -= 1

    if last_possible == -1:
        return 0

    if x[0] >= csum:
        return 0

    last_avail = -1
    ac_sum = 0
    for i in range(len(x)):
        ac_sum += x[i]
        if ac_sum >= csum:
            last_avail = i - 1
            break

    if last_avail == -1:
        last_avail = len(x) - 1

    pos = last_avail

    while pos >= 0:
        if x[pos] < 9:
            break
        pos -= 1

    if pos == -1:
        return 0

    res = list(x)

    res[pos] += 1
    for i in range(pos+1):
        csum -= res[i]

    i = len(res) - 1

    while i > pos:
        res[i] = min(9, csum)
        csum -= res[i]
        i -= 1

    if csum > 0:
        i = len(res) - 1
        while i >= 0:
            if res[i] < 9:
                u = min(csum, 9 - res[i])
                res[i] = res[i] + u
                csum -= u
            i -= 1
        if csum > 0:
            return 0

    res2 = 0
    for y in res:
        res2 = res2 * 10 + y

    return res2


for i in range(n):
    bx = b[i]
    cur = bx % 9
    bx -= cur
    while bx > 0:
        cur = cur * 10 + 9
        bx -= 9
    if cur <= last:
        cur = build_greater(b[i], str(last))
        if cur <= last:
            cur = build_smallest(b[i], len(str(last)) + 1)


    print(cur)
    last = cur


#input = open("input.txt").readline
#f = open("output.txt", "w")

def greedy(le, su):
    if su > le * 9:
        return None
    l = []
    while su > 0:
        if su <= 9:
            l.append(su)
            su = 0
        else:
            l.append(9)
            su -= 9
    for i in range(le - len(l)):
        l.append(0)
    return l[::-1]


def get(li):
    st = ""
    for i in li:
        st += str(i)
    if st == "":
        st = "0"
    return st


mi = [0]  # mi is OK ans
mi_str = "0"

const = "9" * 500

n = int(input())

for i in range(n):
    s = int(input())
    for j in range(len(mi), -1, -1):
        begin = mi[:j]
        begin_sum = sum(begin)
        mi_can = const
        for dig in range(1, 10):
            if begin_sum + dig > s:
                continue
            g = greedy(len(mi) - j - 1, s - begin_sum - dig)
            if g is None:
                continue
            if begin_sum + dig + sum(g) != s:
                continue
            g = begin + [dig] + g
            g_str = get(g)
            if int(mi_str) <= int(g_str) < int(mi_can):
                mi_can = g_str
                continue
        if mi_can != const:
            print(mi_can)
            mi_str = str(int(mi_can) + 1)
            mi = list(map(int, mi_str))
            break
    else:
        g_str = const
        for dig in range(1, 10):
            g = greedy(len(mi), s - dig)
            c = 1
            while g is None:
                g = greedy(len(mi) + c, s - dig)
                c += 1
            g = [dig] + g
            can = get(g)
            if int(can) < int(g_str):
                g_str = can
        mi_str = g_str
        print(mi_str)
        mi_str = str(int(mi_str) + 1)
        mi = list(map(int, mi_str))

digs, a, le = [0] * 333, 0, 0
for _ in range(int(input())):
    b = int(input())
    delta, a = b - a, b
    for i, d in enumerate(digs):
        if d < 9 and 0 < delta <= 9 * i + 9 - d:
            break
        delta += d
        digs[i] = 0
    digs[i] += 1
    le = max(le, i)
    i, delta = divmod(delta - 1, 9)
    digs[:i] = [9] * i
    digs[i] += delta
    print(''.join(map(str, digs[le::-1])))


# written with help of editorial
def get_smallest(dig_sum):
    ret = str(dig_sum % 9) + '9' * (dig_sum // 9)
    return int(ret)

def f(n):
    ret = 0
    while n:
        ret += n % 10
        n //= 10
    return ret

def nx(n):
    s = str(n)
    sm = 0
    for i in range(len(s) - 1, -1, -1):
        if s[i] < '9' and sm > 0:
            return int(s[:i] + str(int(s[i]) + 1) + \
                    str(get_smallest(sm - 1)).zfill(len(s) - i - 1))
        sm += int(s[i])

    return int('1' + str(get_smallest(sm - 1)).zfill(len(s)))

def after(d, low):
    s = '0' * 600 + str(low)
    n = len(s)

    has = f(low)
    for i in range(n - 1, -1, -1):
        has -= int(s[i])
        for x in range(int(s[i]) + 1, 10):
            if s[i] < '9' and has + x <= d <= has + x + 9 * (n - i - 1):
                if i == n - 1:
                    return int(s[:i] + str(x))
                return int(s[:i] + str(x) + \
                        str(get_smallest(d - has - x)).zfill(n - i - 1))

n = int(input())
low = 0
for i in range(n):
    ds = int(input())
    cur = after(ds, low)
    print(cur)
    low = cur



#!/usr/bin/env python

def add(c, v, p=0):
    assert(v < 10 and p < len(c))
    for i in range(p, len(c)):
        c[i] += v
        if c[i] >= 10:
            c[i] %= 10
            v = 1
        else:
            return
    c.append(v)

def find_min(xsum, l):
    csum = sum(l)
    if csum == xsum:
        return l

    if csum < xsum:
        for i, e in enumerate(l):
            delta = min(9 - e, xsum - csum)
            l[i] += delta
            csum += delta
        while csum != xsum:
            delta = min(9, xsum - csum)
            l.append(delta)
            csum += delta
    else:
        for i in range(0, len(l)):
            c = l[i]
            if c != 0:
                delta = 10 - c
                add(l, delta, i)
                csum = sum(l)
                if csum <= xsum:
                    return find_min(xsum, l)

n = int(input())

c = [0]
for i in range(n):
    b = int(input())
    find_min(b, c)
    print(''.join(map(str, c[::-1])))
    add(c, 1)


def getnum(digsum):
    if digsum < 0:
        return 0
    if digsum < 10:
        return digsum
    else:
        nnine = digsum // 9
        res = digsum % 9
        for i in range(nnine):
            res = 10 * res + 9
        return res

def digsumf(n):
    return sum([int(i) for i in str(n)])

def getnext(bnum, last):
    if last == 0:
        return getnum(bnum)

    k = last + 1
    digsum = digsumf(k)
    diff = bnum - digsum
    if diff >= 0 and 9 - k % 10 >= diff:
        return k + diff

    omitsum = 0
    startdigsum = digsumf(last)
    lastl = [int(i) for i in str(last)]
    digsum = digsumf(last)
    l = 10
    i = 1
    while True:
        if i == 1 and len(str(l)) - 1 <= len(lastl):
            omitsum += lastl[-(len(str(l)) - 1)]
        if (last // l) % 10 + i > 9:
            l *= 10
            i = 1
            continue
        k = (last // l) * l + l * i
        digsum = startdigsum - omitsum + i
        diff = bnum - digsum
        r = getnum(diff)
        if diff >= 0 and len(str(r)) <= len(str(l // 10)):
            return r + k
        if diff < 0:
            l *= 10
            i = 1
        else:
            i += 1

n = int(input())
last = 0
for i in range(n):
    last = getnext(int(input()), last)
    print(last)


digs, a, le = [0] * 333, 0, 0
for _ in range(int(input())):
    b = int(input())
    delta, a = b - a, b
    for i, d in enumerate(digs):
        if d < 9 and 0 < delta <= 9 * i + 9 - d:
            break
        delta += d
        digs[i] = 0
    digs[i] += 1
    le = max(le, i)
    i, delta = divmod(delta - 1, 9)
    digs[:i] = [9] * i
    digs[i] += delta
    print(''.join(map(str, digs[le::-1])))

def cr_mn(sm):
    d = 1
    res = 0
    while sm > 0:
        res += min(9, sm) * d
        sm -= min(9, sm)
        d *= 10
    return res

def cr_ln(sm, ln):
    if sm == 0:
        return '0' * ln
    res = int('1' + '0' * (ln - 1))
    d = 1
    sm -= 1
    while sm > 0:
        res += min(9, sm) * d
        sm -= min(9, sm)
        d *= 10
    return str(res)

def cr_min(sm, lst):
    r1 = cr_mn(sm)
    if r1 > int(lst):
        r1 = str(r1)
        return '0' * (len(lst) - len(r1)) + str(r1)
    ln = len(lst)
    lfs = int(lst[0])
    if lfs >= sm:
        return '-1'
    if ln == 1:
        return sm
    r1 = cr_min(sm - lfs, lst[1:])
    if r1 == '-1':
        if lfs == 9:
            return '-1'
        r1 = str(cr_mn(sm - lfs - 1))
        return str(lfs + 1) + '0' * (ln - 1 - len(r1)) + r1
    return lst[0] + r1

n = int(input())
a = []
for i in range(n):
    a += [int(input())]
b = [-1 for i in range(n)]
b[0] = str(cr_mn(a[0]))
print(b[0])
for i in range(1, n):
    b[i] = cr_min(a[i], b[i - 1])
    if b[i] == '-1':
        b[i] = cr_ln(a[i], len(b[i - 1]) + 1)
    print(b[i])


toInt = lambda x : int(''.join(map(str,x[-1::-1])))
import sys
#sys.stdin=open('note.txt')
pre=0
ans=[0]*1000
sum=0
for n in range(int(input())):
    sum=int(input())
    d=sum-pre
    pre=sum
    if d>0:
        for i,dig in enumerate(ans):
            if d+dig<=9:
                ans[i]=dig+d
                break
            d-=9-dig
            ans[i]=9
        print(toInt(ans))
    else: #d is minus
        d=-d+1
        d2=0
        for i, dig in enumerate(ans):
            d2+=dig
            ans[i]=0
            if ans[i+1]<9 and d2>=d:
                break

        ans[i+1]+=1
        d2-=d
        cnt = d2//9
        ans[:cnt]=[9]*cnt
        ans[cnt]=d2 % 9

        print(toInt(ans))


def fill9(x,u):
    k=x//9
    for i in range(k):
        u[i]=9
    if x%9:
        u[k]=x%9
        return k+1
    else:
        return k
n=input()
n=int(n)
u=[0 for i in range(300//9*150+150)]
k=1
for i in range(n):
    x=input()
    x=int(x)
    t=k-1
    while t>=0:
        if u[t]+9*t<x:
            t=fill9(x,u)
            if t>k:
                k=t
            break
        elif u[t]>=x:
            t+=1
            u[t]+=1
            x-=1
            while u[t]==10:
                u[t]=0
                t+=1
                u[t]+=1
                x+=9
            if t+1>k:
                k=t+1
            for t in range(fill9(x,u),t):
                u[t]=0
            break
        else:
            x-=u[t]
            t-=1
    v=[str(j) for j in u[k-1:-len(u)-1:-1]]
    print(''.join(v))

def min_number(sum_digits):
    res = 0;
    base = 1
    while sum_digits > 9:
        res += 9 * base
        base *= 10
        sum_digits -= 9
    res += sum_digits * base
    return res

def from_digits(d):
    res = 0
    base = 1
    for digit in d:
        res += digit * base
        base *= 10
    return res
        
def next_number(x, sum_digits):
    if min_number(sum_digits) > x:
        return min_number(sum_digits)
    
    sd = sum_digits
    x_digits = []
    while x:
        x_digits.append(x % 10)
        x //= 10
    
    if sum_digits > sum(x_digits):
        res_digits = x_digits[::]
        i = 0
        while sum(res_digits) < sum_digits:
            while res_digits[i] == 9:
                i += 1
            res_digits[i] += 1
        return from_digits(res_digits)
    
    x_digits.append(0)
    d = x_digits[::-1]
    
    res_digits = [0] * len(d)
    last_incable = 0
    for i in range(0, len(d)):
        if sum_digits > d[i]:
            res_digits[i] = d[i]
            sum_digits -= d[i]
            if d[i] != 9:
                last_incable = i
        else:
            break
    
    d[last_incable] += 1
    for i in range(last_incable + 1, len(d)):
        d[i] = 0
    rest = sd - sum(d)
    res = from_digits(d[::-1]) + min_number(rest)
    return res

def solve(b):
    r = min_number(b[0])
    print(r)
    for i in range(1, len(b)):
        r = next_number(r, b[i])
        print(r)

n = int(input())
b = [0] * n
for i in range(0, n):
    b[i] = int(input())

solve(b)


n = int(input())
prv = 0
r = [0] * 500
p = 0
for i in range(n):
    x = int(input())
    if x > p:
        d = x - p
        i = 0
        while d > 0:
            e = min(d, 9 - r[i])
            r[i] += e
            d -= e
            i += 1
    else:
        d = p - x + 1
        i = 0
        s = 0
        while d > s or r[i] == 9:
            s += r[i]
            i += 1
        j = 0
        d = s - d
        while j < i:
            e = min(d, 9)
            r[j] = e
            d -= e
            j += 1
        while r[i] == 9:
            i += 1
        r[i] += 1
    s = ''.join(map(str, reversed(r)))
    print(s.lstrip('0'))
    p = x


n = int(input())
prv = 0
r = [0] * 500
p = 0
for i in range(n):
    x = int(input())
    if x > p:
        d = x - p
        i = 0
        while d > 0:
            e = min(d, 9 - r[i])
            r[i] += e
            d -= e
            i += 1
    else:
        d = p - x + 1
        i = 0
        s = 0
        while d > s or r[i] == 9:
            s += r[i]
            i += 1
        j = 0
        d = s - d
        while j < i:
            e = min(d, 9)
            r[j] = e
            d -= e
            j += 1
        while r[i] == 9:
            i += 1
        r[i] += 1
    s = ''.join(map(str, reversed(r)))
    print(s.lstrip('0'))
    p = x


# -*- coding: utf-8 -*-
"""
Created on Mon Nov 30 12:04:02 2015

@author: Mary
"""
n = int(input())
prev_b = 0
r = [0] * 500

for _ in range(n):

    b = int(input())
    
    if b > prev_b:        
        delta = b - prev_b
        i = 0

        while delta > 0:
            if r[i] < 9:
                delta_i = min(delta, 9 - r[i])
                r[i] += delta_i
                delta -= delta_i
            i += 1
    else:
        max_i = -1
        s = 0
        
        while s < prev_b:
            max_i += 1
            s += r[max_i]

        max_i += 1
        sum_ge_max_i = 0

        i = max_i        
        s = 0

        while b > s + r[i-1]:
            
            s += r[i-1]
            i -= 1
            
            if r[i] < 9:
                max_i = i
                sum_ge_max_i = s
        
        r[max_i] += 1
        sum_ge_max_i += 1

        delta = b - sum_ge_max_i 
        
        for i in range(max_i):
            if delta > 0:
                delta_i = min(delta, 9)
                r[i] = delta_i
                delta -= delta_i
            else:
                r[i] = 0
                
    res = ''.join(map(str, reversed(r)))
    print(res.lstrip('0'))
    
    prev_b = b

def nd(n):
    v = 0
    while n:
        n, v = n // 10, v + 1
    return v
def sd(n):
    v = 0
    while n:
        n, v = n // 10, v + n % 10
    return v
def mina(s):
    d9 = s // 9
    return (s % 9 + 1) * 10 ** d9 - 1
def maxan(s, n):
    v = 0
    for i in range(n - 1, -1, -1):
        c = min(s, 9)
        s -= c
        v += c * 10 ** i
    return v
def minan(s, n):
    d9 = (s - 1) // 9
    return 10 ** d9 - 1 + 10 ** (n - 1) + (s - 1) % 9 * 10 ** d9
def f(s, m):
    a1 = mina(s)
    if a1 > m:
        return a1
    n = nd(m)
    if m >= maxan(s, n):
        return minan(s, n + 1)
    for i in range(n):
        if m // 10 ** i % 10 == 9:
            continue
        x = m - m % 10 ** i + 10 ** i
        sx = sd(x)
        if sx > s:
            continue
        for j in range(i + 1):
            d = x // 10 ** j % 10
            c = min(9 - d, s - sx)
            x += c * 10 ** j
            sx += c
        if sx == s:
            return x
    return minan(s, n + 1)
v = 0
for i in range(int(input())):
    v = f(int(input()), v)
    print(v)

t = [0] * 400
x = k = 0
for q in range(int(input())):
    y = int(input())
    d, x = y - x, y
    j = 0
    while d < 1 or t[j] > min(8, 9 * j + 9 - d):
        d += t[j]
        t[j] = 0
        j += 1
    t[j] += 1
    k = max(k, j)
    a, b = divmod(d - 1, 9)
    t[:a] = [9] * a
    t[a] += b
    print(''.join(map(str, t[k::-1])))

t = [0] * 400
x = k = 0
for q in range(int(input())):
    y = int(input())
    d, x = y - x, y
    j = 0
    while d < 1 or t[j] > min(8, 9 * j + 9 - d):
        d += t[j]
        t[j] = 0
        j += 1
    t[j] += 1
    k = max(k, j)
    a, b = divmod(d - 1, 9)
    t[:a] = [9] * a
    t[a] += b
    print(''.join(map(str, t[k::-1])))


t = [0] * 400
x = k = 0
for q in range(int(input())):
    y = int(input())
    d, x = y - x, y
    j = 0
    while d < 1 or t[j] > min(8, 9 * j + 9 - d):
        d += t[j]
        t[j] = 0
        j += 1
    t[j] += 1
    k = max(k, j)
    a, b = divmod(d - 1, 9)
    t[:a] = [9] * a
    t[a] += b
    print(''.join(map(str, t[k::-1])))


t = [0] * 400
x = k = 0
for q in range(int(input())):
    y = int(input())
    d, x = y - x, y
    j = 0
    while d < 1 or t[j] > min(8, 9 * j + 9 - d):
        d += t[j]
        t[j] = 0
        j += 1
    t[j] += 1
    k = max(k, j)
    a, b = divmod(d - 1, 9)
    t[:a] = [9] * a
    t[a] += b
    print(''.join(map(str, t[k::-1])))


t = [0] * 400
x = k = 0
for q in range(int(input())):
    y = int(input())
    d, x = y - x, y
    j = 0
    while d < 1 or t[j] > min(8, 9 * j + 9 - d):
        d += t[j]
        t[j] = 0
        j += 1
    t[j] += 1
    k = max(k, j)
    a, b = divmod(d - 1, 9)
    t[:a] = [9] * a
    t[a] += b
    print(''.join(map(str, t[k::-1])))


t = [0] * 400
x = k = 0
for q in range(int(input())):
    y = int(input())
    d, x = y - x, y
    j = 0
    while d < 1 or t[j] > min(8, 9 * j + 9 - d):
        d += t[j]
        t[j] = 0
        j += 1
    t[j] += 1
    k = max(k, j)
    a, b = divmod(d - 1, 9)
    t[:a] = [9] * a
    t[a] += b
    print(''.join(map(str, t[k::-1])))


t = [0] * 400
x = k = 0
for q in range(int(input())):
    y = int(input())
    d, x = y - x, y
    j = 0
    while d < 1 or t[j] > min(8, 9 * j + 9 - d):
        d += t[j]
        t[j] = 0
        j += 1
    t[j] += 1
    k = max(k, j)
    a, b = divmod(d - 1, 9)
    t[:a] = [9] * a
    t[a] += b
    print(''.join(map(str, t[k::-1])))


t = [0] * 400
x = k = 0
for q in range(int(input())):
    y = int(input())
    d, x = y - x, y
    j = 0
    while d < 1 or t[j] > min(8, 9 * j + 9 - d):
        d += t[j]
        t[j] = 0
        j += 1
    t[j] += 1
    k = max(k, j)
    a, b = divmod(d - 1, 9)
    t[:a] = [9] * a
    t[a] += b
    print(''.join(map(str, t[k::-1])))