Olivia is going to work in the candy shop during the summer. However, she is afraid she’ll have to work at the cash register. Whenever the cash register tells her to return some money to the customer, Olivia panics, because she can’t decide which denominations to use. And if she takes too long (i.e., uses more than p pieces), a long checkout queue of nervous people will soon form.
Problem specification
In this problem we shall consider the Euro, as this is the currency used where Olivia lives.
The cash register holds an infinite supply of each of the following denominations: 1c, 2c, 5c, 10c, 20c, 50c, 1 Euro, 2 Euro, 5 Euro, 10 Euro, 20 Euro, 50 Euro, and 100 Euro. (The “c” denotes cents. There are 100 cents in 1 Euro.)
For the given sum s, find one way of paying s using at most p pieces of currency.
In the easy subproblem A1, p equals 106.
In the hard subproblem A2, p equals 200. (Using fewer pieces is harder!)
In both subproblems, each s will be between 0 and 100 Euro, inclusive.
Input specification
The first line of the input file contains an integer t ≤ 100 specifying the number of test cases. Each test case is preceded by a blank line.
Each test case consists of a single line containing two space-separated integers: e and c. The sum s for this test case is “e Euro c cents”. You may assume that 0 ≤ c ≤ 99.
Output specification
For each test case, output one line containing 13 space-separated integers n1 through n13, where each ni represents the number of pieces of the i-th currency type in the list above. That is, n1 is the number of 1c coins, …, and n13 is the number of 100 Euro banknotes Olivia should use.
The total number of pieces of currency you use (n1 + ⋯ + n13) must be less than or equal to p. Any such output that pays exactly the desired sum s will be considered correct.
Example
In the first test case, Olivia pays “10 Euro 50 cents” using a 10-Euro banknote and a 50-cent coin. In the second test case, she pays a single cent using a 1-cent coin. In the last test case, she pays the sum “18 Euro 47 cents” as 10 Euro + 5 Euro + 2 Euro + 1 Euro + 20 cents + 20 cents + 5 cents + 2 cents.
Note: Please do NOT submit any programs.
For each subproblem, just produce and submit a correct output file.