← 返回题目列表

Codeforces · 509/C

C. 数字总和

中文机器翻译题面 查看原题

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