题目描述

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

高橋君最初持有 $10^{100}$ 张 $1000$ 元纸币、$0$ 枚硬币，之后进行了 $N$ 次购物。

第 $i$ 次购物买了价值 $A_i$ 元的商品。付款时，他只用 $1000$ 元纸币支付，且使用使总金额不少于 $A_i$ 元的最少张数；找零时，收到的硬币总枚数最少。

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

输入格式

N
A_1 ... A_N

输出格式

按 $1$ 元硬币、$10$ 元硬币、$100$ 元硬币的顺序，输出 $N$ 次购物结束时高橋君持有的枚数，用空格隔开。

输入示例 1

3
1296 110 1

输出示例 1

13 18 24

示例 1 说明

• 第 $1$ 次：$1296$ 元，付 $2$ 张纸币（$2000$ 元），找零 $704$ 元 $=$ $7$ 枚 $100$ 元 $+$ $4$ 枚 $1$ 元；
• 第 $2$ 次：$110$ 元，付 $1$ 张纸币，找零 $890$ 元 $=$ $8$ 枚 $100$ 元 $+$ $9$ 枚 $10$ 元；
• 第 $3$ 次：$1$ 元，付 $1$ 张纸币，找零 $999$ 元 $=$ $9 + 9 + 9$ 枚。

累计：$1$ 元硬币 $4+0+9=13$ 枚，$10$ 元硬币 $0+9+9=18$ 枚，$100$ 元硬币 $7+8+9=24$ 枚。

注意 $A_i$ 可以超过 $1000$（第 $1$ 次就是 $1296$），此时要付多张纸币。

输入示例 2

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

输出示例 2

52 59 82

示例 2 说明

这组数据里 $A_i$ 跨越了 $1$ 位到 $5$ 位，既有 $9$、$3$ 这种极小值，也有 $65358$ 这种需要付 $66$ 张纸币的情形，可用来检验张数计算是否正确。

输入示例 3

4
1000 2000 999 1

输出示例 3

10 9 9

示例 3 说明

$A_i$ 恰好是 $1000$ 的倍数时（第 $1$、$2$ 次），付的纸币金额正好等于商品价格，找零为 $0$，一枚硬币都不会拿到。第 $3$ 次找零 $1$ 元（$1$ 枚 $1$ 元硬币），第 $4$ 次找零 $999$ 元（$9+9+9$ 枚）。合计 $1$ 元硬币 $1+9=10$ 枚，$10$ 元与 $100$ 元硬币各 $9$ 枚。

这组数据专门用来检验「整除时不要多付一张纸币」这个边界：若把张数写成 $\lfloor A_i/1000 \rfloor + 1$，第 $1$ 次会多找 $1000$ 元，答案就错了。

约束条件

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