Problem Statement

In the Kingdom of AtCoder, three kinds of coins — $1$-yen coins, $10$-yen coins, and $100$-yen coins — and $1000$-yen bills are in circulation.

Takahashi made $N$ purchases, starting from a state where he had $10^{100}$ $1000$-yen bills and $0$ coins.

In the $i$-th purchase, he bought an item worth $A_i$ yen. For the payment, he paid using only the minimum number of $1000$-yen bills such that the total amount paid was at least $A_i$ yen, and received the change so that the total number of coins received as change was minimized.

Find the number of each type of coin that Takahashi has at the point when all $N$ purchases are finished.

Constraints

• $1\leq N \leq 1000$
• $1\leq A_i \leq 10^5$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

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

Output

Output the number of $1$-yen coins, $10$-yen coins, and $100$-yen coins that Takahashi has at the point when the $N$ purchases are finished, in this order, separated by spaces.

3
1296 110 1

13 18 24

In the first purchase, for the payment of $1296$ yen, Takahashi pays with two $1000$-yen bills, and receives seven $100$-yen coins and four $1$-yen coins as change.

In the second purchase, for the payment of $110$ yen, he pays with one $1000$-yen bill, and receives eight $100$-yen coins and nine $10$-yen coins as change.

In the third purchase, for the payment of $1$ yen, he pays with one $1000$-yen bill, and receives nine $100$-yen coins, nine $10$-yen coins, and nine $1$-yen coins as change.

At the point when the three purchases are finished, he has $13$ $1$-yen coins, $18$ $10$-yen coins, and $24$ $100$-yen coins.

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

52 59 82

• Source: AtCoder ABC 475 B