Vasya 有一个严格递增的正整数序列 a1, ..., an。 Vasya 用它构建了一个新的序列 b1, ..., bn,其中 bi 是 ai 的十进制表示形式的数字之和。然后序列 ai 丢失了,剩下的就是序列 bi。
Vasya 想知道数字 ai 会是什么样子。在所有可能的选项中,他喜欢最后一个数字 an 最小的一个序列。帮助 Vasya 恢复初始顺序。
保证这样的序列总是存在。
输入
第一行包含一个整数 n (1 ≤ n ≤ 300)。
接下来的 n 行包含整数 b1, ..., bn — 所需的数字总和。所有 bi 都属于 1 ≤ bi ≤ 300 的范围。
输出
打印 n 个整数,每行一个 - 数字 ai 的正确选项,按顺序排列。序列应该是严格递增的。第 i 个数的各位数字之和应等于 bi。
如果存在多个具有最小可能编号 an 的序列,则打印其中的任何一个。打印不带前导零的数字。
示例
输入 #1
3 1 2 3
输出 #1
1 2 3
输入 #2
3 3 2 1
输出 #2
3 11 100