403287: GYM101102 G Notes

Memory Limit:256 MB Time Limit:4 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

G. Notestime limit per test4 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Jordanian notes are 1, 5, 10, 20, and 50 JDs.

Maram is going to the shop and has N JDs, she wants to have the money in a form that will allow her to pay for any single item exactly, which means without waiting for change. Given N and the price of each item in the shop, find the required form, that is, find the number of notes of each type she has to have before going to the shop.

Input

The first line of input contains a single integer T, the number of test cases.

The first line of each test case contains two integers N and M (1 ≤ N, M ≤ 105), the amount of money Maram has and the number of items in the shop, respectively. The second line contains M space-separated integers, each value represents the price of an item and is between 1 and N.

Output

For each test case, print five space-separated integers on a single line, where the first integer represents the number of notes of the first type (1 JD), the second integer represents the number of notes of the second type (5 JDs), and so on.

If there’s more than one possible form, find the one that minimizes the total number of notes.

Note that the total amount of money in the printed form should be equal to N.

ExampleInput
2
150 4
150 123 70 20
212 3
1 200 61
Output
5 1 0 2 2
2 0 1 0 4

加入题单

上一题 下一题 算法标签: