Swiss Olympiad in Informatics

In Stofl's office there is an ATM, which belongs to the IBM (International Bank of Mice). Stofl has a lot of coworkers and so the ATM in their office is used quite frequently (on good days almost 10'000 times), therefore there is a good chance that there will be an error somewhere on the way.

In order to be able to detect such an error, you will write a computer program which simulates the withdrawals at the ATM in Stofls office.

Every morning the IBM fills the ATM with a certein amount of bills (1000, 200, 100, 50, 20 and 10 frank bills) as well as coins (5, 2 and 1 frank coins).

The customers of the IBM do not like to have too many small bills or coins. They even prefer not getting any money from this ATM and going to another one to getting too many small bills or coins. Since the IBM does not want angry customers, they programmed their ATMs such that they do not cash out any money if too many small bills/coins would be needed. For example, if a mouse requests 16 franks (so the optimal composition would be 1×10 franks + 1×5 franks + 1×1 franks) and there is no 5 frank coin in the ATM, the ATM does not pay out anything, even if there are, for example, one 10-frank bill and six 1-frank coins in the machine and the withdrawal would in principle be possible.

You are given the detailed amount of bills and coins put into the ATM in the morning and the requested withdrawals for a particular day. Find the amount of bills and coins at the end of the day.

The first line contains nine integers: A₁,…,A₉, the amount of 1000-, 200-, 100-, 50-, 20-, 10-, 5-, 2-, 1-frank bills/coins in the morning of the day to simulate. You can assume that 0≤A_i≤10'000, for i=1..9. The next line contains one integer N (N<10'000), the number of requested withdrawals for this day. The following N lines each contain one integer k_i (0≤k_i≤1'000'000). They describe the requested withdrawals (in chronological order) for this particular day.

Output one line with nine integers, separated by a space each: B₁,…,B₉, the amount of 1000-, 200-, 100-, 50-, 20-, 10-, 5-, 2-, 1-frank bills/coins in the evening of the same day (after the N withdrawals).

0 0 0 0 0 4 3 2 1
6
11
20
3
55
7
4

0 0 0 0 0 3 2 1 0

• For the sample input there are four 10-frank bills, three 5-frank coins, two 2-frank coins and one 1-frank coin and there are six money requests on that day.
• The first withdrawal of 11 franks can be paid exactly by one of the 10-frank bills and the 1-frank coin.
• The withdrawal of 20 franks cannot be paid, since there is no 20-frank bill. Therefore the withdrawal is rejected and no money leaves the ATM, even though there are 3 10-frank bills.
• The following withdrawal of 3 franks cannot be paid, since there are no more 1-frank coins.
• The withdrawal of 55 franks cannot be paid, because there is no 50-frank bill.
• The 7-frank withdrawal is paid by a 5- and a 2-frank coin each.
• The last withdrawal (4 franks) cannot be paid, since there is only one 2-frank coin left.

Submission form