题目描述

在 AtCoder 王国中，流通着 $1$ 日元硬币、$10$ 日元硬币、$100$ 日元硬币这 $3$ 种硬币，以及 $1000$ 日元纸币。

高桥君从持有 $10^{100}$ 张 $1000$ 日元纸币和 $0$ 枚硬币的状态出发，进行了 $N$ 次购物。

第 $i$ 次购物买的是价格为 $A_i$ 日元的商品。 付款时，他只使用「支付总额不小于 $A_i$ 日元的前提下张数最少」的 $1000$ 日元纸币付钱，并按「收到的零钱硬币总数最少」的方式收取找零。

请求出 $N$ 次购物全部结束时高桥君持有的各种硬币的枚数。

输入格式

输入按以下格式从标准输入读入：

• $N$
• $A_1$ $A_2$ $\dots$ $A_N$

输出格式

请按 $1$ 日元硬币、$10$ 日元硬币、$100$ 日元硬币的顺序，用空格分隔，输出 $N$ 次购物全部结束时高桥君持有的各种硬币的枚数。

数据范围

• $1\leq N \leq 1000$
• $1\leq A_i \leq 10^5$
• 所有输入值均为整数。

3
1296 110 1

13 18 24

第 $1$ 次购物中，高桥君为支付 $1296$ 日元，付了 $2$ 张 $1000$ 日元纸币，并收到 $7$ 枚 $100$ 日元硬币和 $4$ 枚 $1$ 日元硬币作为找零。

第 $2$ 次购物中，高桥君为支付 $110$ 日元，付了 $1$ 张 $1000$ 日元纸币，并收到 $8$ 枚 $100$ 日元硬币和 $9$ 枚 $10$ 日元硬币作为找零。

第 $3$ 次购物中，高桥君为支付 $1$ 日元，付了 $1$ 张 $1000$ 日元纸币，并收到 $9$ 枚 $100$ 日元硬币、$9$ 枚 $10$ 日元硬币和 $9$ 枚 $1$ 日元硬币作为找零。

于是，$3$ 次购物结束时，他持有 $13$ 枚 $1$ 日元硬币、$18$ 枚 $10$ 日元硬币、$24$ 枚 $100$ 日元硬币。

12
3141 592 65358 9 79 323 84 6264 3 38327 950 28

52 59 82

• 来源：AtCoder ABC 475 B

子任务设置

• 子任务 1（100 分）：无特殊限制。